当前位置: 首页 > news >正文

蓝桥冲刺31天之325

把时间分给睡眠,分给书籍,分给运动

分给花鸟树木和山川湖海

分给你对这个世界的热爱

123 

题目描述

小蓝发现了一个有趣的数列,这个数列的前几项如下:

1,1,2,1,2,3,1,2,3,4,⋯

小蓝发现,这个数列前 1 项是整数 1,接下来 2 项是整数 1 至 2,接下来 3 项是整数 1 至 3,接下来 4 项是整数 1 至 4,依次类推。

小蓝想知道,这个数列中,连续一段的和是多少。

输入描述

输入的第一行包含一个整数 T,表示询问的个数。

接下来 T 行,每行包含一组询问,其中第 i 行包含两个整数 li​ 和 ri​,表示询问数列中第 li​ 个数到第 ri​ 个数的和。

输出描述

输出 T 行,每行包含一个整数表示对应询问的答案。

输入输出样例

示例

输入

3
1 1
1 3
5 8

输出

1
4
8

评测用例规模与约定

对于 10% 的评测用例,1≤T≤30,1≤li​≤ri​≤100。

对于 20% 的评测用例,1≤T≤100,1≤li​≤ri​≤1000。

对于 40% 的评测用例,1≤T≤1000,1≤li​≤ri​≤10^6。

对于 70% 的评测用例,1≤T≤10000,1≤li​≤ri​≤10^9。

对于 80% 的评测用例,1≤T≤1000,1≤li​≤ri​≤10^12。

对于 90% 的评测用例,1≤T≤10000,1≤li​≤ri​≤10^12。

对于所有评测用例,1≤T≤100000,1≤li​≤ri​≤10^12。

题目解析:

 我们可以把原序列分割为:

1      1/2     1/2/3      1/2/3/4     1/2/3/4/5      1/2/3.../n

这样子的话每一个都是可以做成前缀和的形式,我们只需要判断左右端点在哪个区间位置里即可,然后我们再把每一个区间内的数再一次进行前缀和,可以直接获得左右端点所在的区间内的总和,然后再去计算两个数在各自区间内的总和即可
左右端点所在区间可以通过二分去获得

具体代码如下,没懂可以留言

参考代码: 

import java.io.*;

/**
 * @ClassName 一二三
 * @Description TODO
 * @Author 小怂很怂
 * @Date 2023/3/25 13:37
 * @Version 1.0
 **/
public class 一二三 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
    static long []arr=new long[1500010];
    static long []brr=new long[1500010];
    public static void main(String[] args) throws Exception {
        int t=nextInt();
        for (int i=1;i<=1500000;i++){
            arr[i]+=i+arr[i-1];
            brr[i]=brr[i-1]+arr[i];
        }
        for (int i=0;i<t;i++){
            long a=nextLong(),b=nextLong(),sum=0,x,y;
            x=pd(a);//判断位置
            y=pd(b);
            if (x==y){//在同一个区间内
                sum=(b-arr[Math.toIntExact(x - 1)]+1)*(b-arr[Math.toIntExact(x - 1)])/2;//在同一区间中,1----b对应数的和
                sum-=(a-arr[Math.toIntExact(x-1)])*(a-arr[Math.toIntExact(x-1)]-1)/2;//减去1---a-1对应数的和
            }else {
                sum += ((brr[Math.toIntExact(y-1)] - brr[Math.toIntExact(x - 1)]));
                sum-=(a-arr[Math.toIntExact(x-1)])*(a-arr[Math.toIntExact(x-1)]-1)/2;//减去1---a-1对应数的和
                sum+=(b-arr[Math.toIntExact(y - 1)]+1)*(b-arr[Math.toIntExact(y - 1)])/2;//在同一区间中,1----b对应数的和
            }
            System.out.println(sum);
        }
        pw.flush();
    }
    public static long pd(long a){
        int l=1;
        int r=1500000;
        int mid;
        while (l<r){
            mid=(l+r)/2;
            if (arr[mid]>=a&&arr[mid-1]<a){
                return mid;//说明这个数在第mid区间
            }else if (arr[mid]>a){//说明这个值比它大,在前面
                r=mid-1;
            }else if (arr[mid]<a){//在后面
                l=mid+1;
            }
        }
        return r;
    }
    public static int nextInt() throws Exception {//int型
        st.nextToken();
        return (int) st.nval;
    }

    public static long nextLong() throws Exception {//long型
        st.nextToken();
        return (long) st.nval;
    }
}

 求阶乘

问题描述

满足 N ! 的末尾恰好有 K 个 0 的最小的 N 是多少?

如果这样的 N 不存在输出 −1 。

输入格式

一个整数 K 。

输出格式

一个整数代表答案。

样例输入

2

样例输出

10

评测用例规模与约定

对于 30% 的数据, 1≤K≤10^6.

对于 100% 的数据1≤K≤10^18.

题目解析:

 N!中有多少个0可以取决于1至N中每一个数公因子分解后2和5的个数

拓展:

1---N中因子s的个数代码如下:

while(n>0){

  sum+=n/s;

  n/=s;

}

同时,通过上面的代码我们可以明确的知道,1----N中,因子2的个数比因子5的个数多,所以我们着重选择5的个数,也就是说,有多少个因子5就会有多少个结尾0

通过二分的方式快速的去寻找N,使得1---N的因子5个数>=k,且1----N-1的因子5个数<k

具体代码如下:

参考代码:

 

import java.io.*;
import java.util.Scanner;

/**
 * @ClassName 求阶乘
 * @Description TODO
 * @Author 小怂很怂
 * @Date 2023/3/25 14:05
 * @Version 1.0
 **/
public class 求阶乘 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception {
        long n=Long.parseLong(br.readLine().trim());
        long r= (long) 4e18;
        long l=1;
        while(l<r){
            long mid=(l+r)/2;
            if (pd(mid)>=n) r=mid;
            else l=mid+1;
        }
        if (pd(l)==n) pw.println(l);
        else pw.println(-1);
        pw.flush();
    }
    public static long pd(long num){
        long sum=0;
        while (num>0){
            sum+=num/5;
            num/=5;
        }
        return sum;
    }
    public static int nextInt() throws Exception {//int型
        st.nextToken();
        return (int) st.nval;
    }

    public static long nextLong() throws Exception {//long型
        st.nextToken();
        return (long) st.nval;
    }
}

相关文章:

  • 不确定的市场,确定的增长,海尔智家2022全球再逆增
  • 高校智慧校园建设案例|某药科大学智慧校园建设实践
  • Python 3.7 有什么新变化 - 新功能
  • 【每日一题Day166】LC1053交换一次的先前排列 | 贪心
  • 蓝桥杯 --- 递归与递推(习题)
  • Ubuntu搭建web站点并发布公网访问【内网穿透】
  • 【我在异世界学Linux】认识操作系统 | 理解管理 | 系统调用(System Call)
  • 【Elastic (ELK) Stack 实战教程】07、Logstash 快速入门及 Input、Filter 插件讲解
  • 版本控制 | 告别繁琐,P4VJS带来全新的Diff体验
  • 老鼠迷宫,汉诺塔,八皇后,回溯算法案例
  • MATLAB :【12】手把手教你在Linux以命令行方式(静默方式/非图形化方式)安装MATLAB(正版)
  • 数据库MySQL/Navicat+商品购物系统+Java实现(超详细讲解)
  • 大文件分片上传的实现【前后台完整版】
  • Chatgpt 指令收集
  • 2022国赛14:2022国赛正式题域控制器的迁移
  • 【IAR工程】STM8S208RB基于ST标准库内部EEPROM使用
  • springcloud整合knike4j聚合微服务接口文档
  • 学会这些方法,扩展磁盘分区还不是轻轻松松?
  • Chat GPT和飞书机器人,真的有那么多联系嘛?
  • Pikachu登录爆破之token爆破解析
  • 电加热油锅炉工作原理_电加热导油
  • 大型电蒸汽锅炉_工业电阻炉
  • 燃气蒸汽锅炉的分类_大连生物质蒸汽锅炉
  • 天津市维修锅炉_锅炉汽化处理方法
  • 蒸汽汽锅炉厂家_延安锅炉厂家
  • 山西热水锅炉厂家_酒店热水 锅炉
  • 蒸汽锅炉生产厂家_燃油蒸汽发生器
  • 燃煤锅炉烧热水_张家口 淘汰取缔燃煤锅炉
  • 生物质锅炉_炉
  • 锅炉天然气_天燃气热风炉