这题明白的意思就是求n!在b进制下的后缀零的个数。
即最大的n!%(b^k)==0的k的值。我们需要将如果要构成b这个数，肯定是由一个个质因子相乘得到的。我们只需要求出b的质因子，然后分析n!中可以组成一个b的因子由多少个就可以了。
因为b是10的12次方，所以b的质因子某个因子大于了10的6次方，那肯定是质数了，所以我们只需要筛选出10的6次方以内的质因子就可以了，并且记录下每个质因子的基数。
最后是记录n!由多少个b的素因子组成并除以它的基数，取其中的最小值。
n!中有多少个素因子(假设素因子是x),我们只需要算出1到n中所有a*x^b(a<x)的b的总和,我们不必将某个x^b一个个算出来，我们只需要算出(n/x)到(n/x^b)的总和即可。
附上AC代码（感觉写得不怎么样
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<fstream> using namespace std; typedef long long ll; ll prime[1000005]; struct node { ll num; ll data; } a[1000005];; bool vis[10000005]; ll b; ll init() { memset(vis,false,sizeof(vis)); ll k=0,i; for(i=2; i<=1000000; i++) { if(!vis[i]) { prime[k++]=i; for(ll j=2; i*j<=1000000; j++) vis[i*j]=true; } } return k; } int main() { ll k,i,j,n,cnt,sum,t=78498,r,mini; t=init();//线性筛出质数 while(scanf("%I64d%I64d",&n,&b)!=EOF) { cnt=0; sum=0; r=b; for(i=0; i<t&&b!=1; i++) { if(b%prime[i]==0) { a[cnt].data=prime[i]; a[cnt].num=0; while(b%prime[i]==0) { a[cnt].num++; b/=prime[i]; } cnt++; } } if(b!=1) a[cnt].data=b,a[cnt++].num=1; b=r; for(i=0; i<cnt; i++) { for(j=a[i].data,sum=0,r=1; j<=n; j*=a[i].data) { sum+=(n/j); if(n/j<a[i].data)//为了防止j发生溢出 break; } if(i==0) mini=sum/a[i].num; else mini=min(mini,sum/a[i].num); } printf("%I64d ",mini); } }
）