题目大意： 有一个与阶乘有关的游戏，给出两个整数n ,m ，令t=n!，每轮游戏的流程如下 1.如果 m不能整除t ，即 t mod m !=0 ，跳到第三步；如果能整除，跳到第二步 2.令t=t/m,xyx的得分+1并返回第一步 3.游戏结束 xyx共进行T轮游戏，他想知道每轮他的得分是多少 特别注意，m,n<10e9；
解题思路： 先理解一下题意，其实就是找n中有多少个m，可以先考虑m是质数的情况，发现在n!中，每隔m个数会出现m的倍数，我们只要不停地/m就好了。 那m是合数怎么办？ 可以用筛法把m分解质因数，每次记录当前质因数以及它出现的次数，然后每次算出n中有多少个当前质因数，注意因为可能一个质因数出现多次，最后需要再/p，最后取最小值就可以了。
#include<cstdio> #include<iostream> using namespace std; int T,n,m; int ans; int cal(int p,int a)//求n中有几a个p { int t=0; for (int i=n;i;i/=p) t+=i/p; return t/a; } main() { // freopen("fac.in","r",stdin); // freopen("fac.out","w",stdout); cin>>T; while(T--) { scanf("%d%d",&n,&m); ans=2e9; for (int t,s,i=2;i*i<=m;++i) if (m%i==0) { t=i;s=0; while(m%i==0){//筛法分解质因数 s++; m/=i; } ans=min(ans,cal(t,s)); } if (m>1) ans=min(ans,cal(m,1));//因为筛法枚举的是小于等于根号m的质因数，如果分解后m>1，说明有且仅有一个大于根号m的质因数，特判一下。 printf("%d\n",ans); } }