10061

[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)

*/

#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;
}