Problem Link: LightOJ 1138
We can easily calculate trailing zeros in n!. But, this problem refers to find the smallest n where n! holds exactly k trailing zeros.
If you don’t know how to calculate trailing zeros of n!. Read here – Trailing Zeros.
The max range of k is 10^8. So, 5*10^8! can easily hold this amount of trailing zero ( as the number of total 5 will be= 5*10^8/ 5 + 5*10^8/ (5*5) + 5*10^8/(5*5*5) +…. ). As, the number of trailing zero increases with the increment of n. Now, search for n and check if that contains k trailing zero or not. Factorial of multiple numbers can contain same numbers of trailing zero, in this problem you just have to find the smallest one, which is obviously a multiple of 5. Now, code it and have a green verdict…
Code:
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define ll long long | |
| int main () | |
| { | |
| ll tc,idd=0,b,n,temp,r,i,p,q,c,ans; | |
| scanf("%lld",&tc); | |
| while(tc--) | |
| { | |
| scanf("%lld",&n); | |
| printf("Case %lld: ",++idd); | |
| ans=0; | |
| ll lo=1,hi=5000000000,mid; | |
| while(lo<hi) | |
| { | |
| mid=(lo+hi)/2; | |
| ll cnt=0,tmp=mid; | |
| while(tmp/5) | |
| { | |
| cnt+=tmp/5; | |
| tmp/=5; | |
| } | |
| if(cnt==n) | |
| { | |
| ans=mid; | |
| break; | |
| } | |
| if(cnt<n) | |
| lo=mid+1; | |
| else | |
| hi=mid-1; | |
| } | |
| if(ans) | |
| printf("%lld\n",ans-ans%5); | |
| else | |
| printf("impossible\n"); | |
| } | |
| return 0; | |
| } |
“For every complex problem there is an answer that is clear, simple, and wrong“
— H. L. Mencken
