曾经做过一个类似的 求n！中有多少个质因子m
这里有一个结论 k = n/m+n/(m^2)+n/(m^3)+....
int getnum(int n, int m){ int sum = 0; while(n) { sum += n/m; n /= m; } return sum;} 然后这个题就比较容易了
/************************************************************************* > Author: xlc2845 > Mail: xlc2845@gmail.com > Created Time: 2013年10月24日 星期四 16时15分17秒 ************************************************************************/#include#include #include #include #include #include #include #define maxn 210#define INF 0x7fffffffusing namespace std;bool flag[5010];int prime[5010];void GetPrime(){ memset(flag, 0, sizeof(flag)); int p = 0; for(int i = 2; i < 5001; i++) { if(!flag[i]) { prime[p++] = i; for(int j = i+i; j < 5001; j+=i) flag[j] = 1; } }}int getnum(int n, int m){ int sum = 0; while(n) { sum += n/m; n /= m; } return sum;}int main(){ GetPrime(); int t,n,m,ca = 1; scanf("%d",&t); while(t--) { int p = 0, ans = INF; scanf("%d%d",&m,&n); while(m > 1) { int k = 0; while(m % prime[p] == 0) { k++; m /= prime[p]; } if(k) ans = min(getnum(n, prime[p])/k, ans); p++; } printf("Case %d:\n",ca++); if(ans) printf("%d\n",ans); else puts("Impossible to divide"); } return 0;}