Description
Input
第一行有一个正整数T,表示测试数据的组数。
接下来的T行，每行输入两个十进制整数n和base。
Output
对于每组数据，输出一个十进制整数，表示在base进制下，n!结尾的零的个数。
Sample Input
210 10 10 2
Sample Output
28
Data Constraint
对于20%的数据，n<=20,base<=16
对于50%的数据，n<=10^9,base<=10^5
对于100%的数据，1<=T<=50，0<=n<=10^18，2<=base<=10^12
Solution
答案就是最多的n!可以除的尽的base的个数。
考虑对n!和base分别分解质因数，那么答案就是质因数的指数相除的最小值。
对base可以在根号base的时间内分解，而n!可以在最多log n的时间内完成，因此时间复杂度为
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;i++)
#define Fd(i,a,b) for(I i=a;i>=b;i--)
#define N 1000005
using namespace std;
I T,bz[N],p[80000];
ll n,m,x,cnt,tot,ans;
I main(){freopen("Factorial.in","r",stdin);freopen("Factorial.out","w",stdout);F(i,2,N-5){if(!bz[i]) p[++p[0]]=i;F(j,1,p[0]){if(i*p[j]>N-5) break;bz[i*p[j]]=1;if(i%p[j]==0) break;}}scanf("%d",&T);while(T--){scanf("%lld%lld",&n,&m);ans=1e18;F(i,1,p[0]){if(p[i]>m) break;if(m%p[i]==0){tot=cnt=0;while(m%p[i]==0){m/=p[i],tot++;}x=n;while(x/p[i]){cnt+=x/p[i],x/=p[i];}ans=min(ans,cnt/tot);}}if(m>1){x=n;cnt=0;while(x/m){cnt+=x/m,x/=m;}ans=min(ans,cnt);}printf("%lld\n",ans); }return 0;
}