[highlight]Solution[/highlight]
/*
Now we can break the Base B as a product of primes :
B = a^p1 * b^p2 * c^p3 * …
Then the number of trailing zeroes in N factorial in Base B is given by the formulae
min{1/p1(n/a + n/(a*a) + ….), 1/p2(n/b + n/(b*b) + ..), ….}.
And the number of digits in N factorial is :
floor (ln(n!)/ln(B) + 1)
*/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> #include <math.h> #include <stdio.h> using namespace std; int main() { int N,B; int p,noz; while(cin>>N>>B) { if(N==0 && B==0) cout<<268435456<<" "<<1<<"\n"; if(N==0 && B==1) cout<<0 <<" "<<0<<"\n"; if(N==1 && B==2) cout<<0<<" "<<1<<"\n"; if(N==1 && B==0) cout<<268435456<<" "<<1<<"\n"; if(N==1 && B==1) cout<<1<<" "<<1<<"\n"; int x=B; noz=N; for(int i=2;i<=B;i++) { if(x%i==0) { p=0; while(x%i==0) { p++; x/=i; } int n_N=N; int c=0; while((n_N/i)) { c+=n_N/i; n_N/=i; } noz=min(noz,c/p); } } //cout<<noz; double ans=0; for(int i=1;i<=N;i++) { ans+=log10(i); } ans=ans/log10(B); cout<<noz<<" "; printf("%.0lf\n",floor(ans+ 1e-9)+1);//<<ans<<"\n"; } return 0; } |