SGU-154 Factorial (末尾0 & 三分）

154. Factorial

time limit per test: 0.25 sec. memory limit per test: 4096 KB

input: standard input output: standard output

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 1*2*...*N. For example, 5! = 120, 120 contains one zero on the trail.

Input

One number Q written in the input (0<=Q<=10^8).

Output

Write "No solution", if there is no such number N, and N otherwise.

Sample test(s)

Input

2

Output

10

分析：要求出n!的末尾0的个数也就是寻找n!中5的个数，如5！的5因子个数是1，15！的5因子的个数是3，25的5因子个数是6，可以得到这样的

递推式s[n!]=n/5+s[(n/5)!]。在(0<=Q<=10^8)内寻找这样的值n，为了抢时间用

三分：

#includeusing namespace std;const int maxn=4e8+15;int sum;int getnum(int n){ if(n==0)return 0; sum=n/5+getnum(n/5); return sum;}int ternarysearch(int low,int high,int x){ int res; if(highq2) res=ternarysearch(mid2+1,high,x); else res=ternarysearch(mid1+1,mid2-1,x); } return res;}int main(){ //freopen("cin.txt","r",stdin); int n; while(~scanf("%d",&n)){ if(n==0){ printf("1\n"); continue; } int ans=ternarysearch(0,maxn,n); if(ans==-1)printf("No solution\n"); else { ans=ans/5*5; printf("%d\n",ans); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。