蓝桥冲刺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;
}
}