原题
题目描述
给出一个数k,求最小的n,使得n的阶乘后面0的数量>=k。
例如k=1,
5的阶乘 = 1*2*3*4*5 = 120,120后面有1个0。并且4的阶乘后面没有0,所以5是最小的结果。
输入
一个数k(1 <= k <= 10^9)
输出
输出最小的满足条件的n。
输入样例
1
输出样例
5
题解
又是一道二分答案题。
这次直接干V2版本。(V1版通用)
先在前面说一下,这道题需要使用long long,否则会WA掉几个值
这道题最先考虑的是如何判断它末尾有几个0。
没错,又是找规律
末尾0的构成要有2和5这两个数
例如:
10=2*5
100=4*5*5
……
因为2的倍数比5的倍数多得多
所以,我们只需要考虑5的倍数有几个就可以知道末尾有几个0。
(注意25这一类数,等于5*5,算是两个5的倍数)
规律找出来了。
然后是二分
我们可以将5的倍数进行二分,也就是最后的答案。
如果这个二分的答案满足k,就把二分的值调小
如果这个二分的答案不满足k,就把这个值调大
bingo,问题解决!
先来看看check函数的代码
1 bool check(long long x){
2 long long p=x,num=0;
3 while(p!=0)
4 {
5 p/=5;
6 num+=p;
7 }
8 if(num>=k)
9 return 1;
10 else
11 return 0;
12 }
下面是整个题目的代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<cstring>
5 #include<algorithm>
6 #define inf 100000000
7 using namespace std;
8 long long k;
9 bool check(long long x){
10 long long p=x,num=0;
11 while(p!=0)
12 {
13 p/=5;
14 num+=p;
15 }
16 if(num>=k)
17 return 1;
18 else
19 return 0;
20 }
21 int main()
22 {
23 cin>>k;
24 long long l,r,m;
25 l=0;r=1e12+1;
26 while(l<r-1)
27 {
28 m=(l+r)/2;
29 if(check(m))
30 r=m;
31 else
32 l=m;
33 }
34 cout<<r;
35 return 0;
36 }