学步园

n!=x*b^y,

当x为正整数时,最大的y就是n!末尾0的个数了,

把n,b分别拆成素因子相乘的形式:

例如,

n=5,b=16

n=5,b=2^4,

很明显,末尾0的个数为0

10进制时,n!=a*10^x

b进制时,n!=c*b^y

很明显,n!的位数就是最大的x+1

这里计算我用了log,精度设置为1e-9

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
const int inf=(1<<31)-1;
const double eps=1e-9;
vector<int>prime;
void maketable()
{
    int i,j,n=800;
    bool iscp[810];
    memset(iscp,0,sizeof(iscp));
    for(i=2;i<=n;i++)
    {
        if(!iscp[i])
        {
            prime.push_back(i);
            for(j=i+i;j<=n;j+=i)
                iscp[j]=1;
        }
    }
}
map<int,int>fn;
map<int,int>fb;
map<int,int>::iterator it;
void debug()
{
    cout<<"***************"<<endl;
    for(it=fn.begin();it!=fn.end();it++)
        cout<<it->first<<"^"<<it->second<<endl;
    cout<<"***************"<<endl;
     for(it=fb.begin();it!=fb.end();it++)
        cout<<it->first<<"^"<<it->second<<endl;
     cout<<"***************"<<endl;
}
int main()
{
    //freopen("in","r",stdin);
    //freopen("out","w",stdout);
    maketable();
    int i,j,k,n,b,dg,m,num_zero;
    double x;
    while(cin>>n>>b)
    {
        fn.clear();
        fb.clear();
        x=0;
        for(i=2;i<=n;i++)
            x+=log10(double(i));
        dg=int(x/log10(double(b))+eps)+1;
        m=prime.size();
        for(i=2;i<=n;i++)
        {
            k=i;
            for(j=0;j<m&&k>=prime[j];j++)
            {
                while(k%prime[j]==0&&k>=prime[j])
                {
                    fn[prime[j]]++;
                    k/=prime[j];
                }
            }
        }
        for(i=0;i<m&&b>=prime[i];i++)
        {
            while(b%prime[i]==0&&b>=prime[i])
            {
                fb[prime[i]]++;
                b/=prime[i];
            }
        }
        //debug();
        num_zero=inf;
        for(it=fb.begin();it!=fb.end();it++)
            num_zero=min(num_zero,fn[it->first]/it->second);
        cout<<num_zero<<" "<<dg<<endl;
    }
    return 0;
}