题目大意：让求n！在base进制下的位数以及末尾0的连续个数。
题目分析：一个m位的b进制数N，最小是b^(m-1)，最大不超过b^m，即b^(m-1)≤N<b^m。解不等式，得log10(N)/log10(b)<m≤log10(N)/log10(b)+1。
至于0的个数，要对n！分解质因数，对base分解质因数。看n！的质因数中能凑出多少个base。能凑出的base的个数就是末尾0的个数。设n！与base的共同质因数所构成的集合为s1。base的质因数构成的集合为s2，则末尾0的个数就是min(s1(s2(i))/s2(i))。
其实，这道题无非就是多个算法的整合。筛素数+大整数分解质因数。
代码如下：
# include<iostream> # include<cstdio> # include<cmath> # include<map> # include<cstring> # include<algorithm> using namespace std; const int N=1<<20; double a[N+50]; int pri[150],mark[800]; map<int,int>m[805]; void init() { a[1]=log10(1.0); for(int i=2;i<=N;++i) a[i]=a[i-1]+log10(i); for(int i=2;i<=800;++i){ int n=i; int a=2; while(a*a<=n){ while(n%a==0){ ++m[i][a]; n/=a; } ++a; } if(n>1) ++m[i][n]; } pri[0]=0; memset(mark,0,sizeof(mark)); for(int i=2;i<=800;++i){ if(!mark[i]) pri[++pri[0]]=i; for(int j=1;j<=pri[0]&&i*pri[j]<=800;++j){ mark[i*pri[j]]=1; if(i%pri[j]==0) break; } } } int f(int n,int k) { map<int,int>mp; for(int i=2;i<=n;++i){ int n=i; for(int j=1;j<=pri[0]&&pri[j]<=k;++j){ while(n%pri[j]==0){ ++mp[pri[j]]; n/=pri[j]; } } } map<int,int>::iterator it; int ans=1<<30; for(it=m[k].begin();it!=m[k].end();++it){ ans=min(ans,mp[it->first]/(it->second)); } return ans; } int g(int n,int k) { double ans=a[n]/log10(k)+1.0; return (int)ans; } int main() { init(); int n,k; while(scanf("%d%d",&n,&k)!=EOF) { printf("%d %d ",f(n,k),g(n,k)); } return 0; }