原题
题目描述
给出一个数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 }