代码拉取完成，页面将自动刷新
蓝桥杯题库 题目链接。
二分，数论，省赛，2022
这题的关键有两个：求阶乘的方式和二分法。如果单纯的用暴力循环会超时。
计算n的阶乘后面有多少个0？
两个大数字相乘，都可以拆分成多个质数相乘，而质数相乘结果尾数为0的，只可能是2*5。因为每两个连续数字就会有一个因子2，个数比5多得多，所以只关心有多少个5就行了。
由题意可知我们要求最小的 $ N! $ 的后缀 0 的个数恰好等于 k 的个数，根据唯一分解定理可知我们可以把阶乘分解成若干个素数的乘积。
因为我们统计的是 $ N $ 阶乘后缀 $ 0 $ 的个数，即我们求 $ N $ 的阶乘 $ 10 $ 的因子的个数，因子 $ 10 $ 必须由质因子 $ 2 $ 和质因子 $ 5 $ 相乘所得，所以要求 $ N $ 的阶乘的质因子中含有若干对2和5 ,于是我们把题意转化为求最小的阶乘，并满足该阶乘 $ min(质因子2的个数 , 质因子5的个数) == k $ 。
求 $ N! $ 的质因子 $ p $ 的个数公式 : $ \sum_{i=1}^n\frac{N}{p^i} $ 。
由上式可知，阶乘质因子 2 的个数小于等于质因子 5 的个数，于是我们只统计质因子 5 的个数即可。于是题意转换为求最小的 $ N $ 满足 $ \sum_{i=1}^n\frac{N}{5^i} $ 恰好等于 $ 5 $ 。
时间复杂度为 $ O(n\\ * \log(n)) $ 。
我们观察到 5 的个数对于 $ N! $ 来说是逐渐增加的，满足单调性性质，故我们可以用二分去查找阶乘大于等于k的第一个数 $ N $ , 然后判断查找到的 $ N $ 是否恰好等于 $ k $ 即可 。
二分中的 $ check $ 函数表示 $ x $ 的阶乘的质因子 $ 5 $ 的个数。
时间复杂度为 $ O(\log(n)\\ * \log(n)) $ 。
// 30pts
import java.util.Scanner;
public class Main {
final static int N = (int)1e7 ;
static int get_5(int x) {
int t = x , res = 0 ;
while(t > 0) {
res += t / 5 ; // #
t /= 5 ;
}
return res ;
}
public static void main(String[] args) {
Scanner sc = new Scanner (System.in);
int k = sc.nextInt() ;
for(int i = 1 ; i <= N ; i ++) {
if(get_5(i) >= k) { //找到第一个大于等于k的
if(get_5(i) == k) {
System.out.println(i);
} else {
System.out.println(-1);
}
break;
}
}
sc.close();
}
}
// 100pts
import java.util.Scanner;
public class Main {
static long get_5(long x) {
long t = x , res = 0 ;
while(t > 0) {
res += t / 5 ; // #
t /= 5 ;
}
return res ;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in) ;
long k = sc.nextLong() ;
long l = 0L , r = (long)9e18 ;
while(l < r) {
long mid = l + r >> 1 ;
if(get_5(mid) >= k) r = mid ;
else l = mid + 1 ;
}
if(get_5(r) == k)
System.out.print(r) ;
else
System.out.print("-1");
sc.close() ;
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
