给定 m,n ，求最大的 k 使得 m^k∣n!
分解质因数
#include <iostream>
#include <cstring>
#include <sstream>
using namespace std;
const int N =1e4+20;
const int inf =1e9 ;
int n,m,a[N],b[N];
int prime[N],tot,vis[N];
void init(int top){
for(int i=2;i<=top;++i)
if(vis[i]==0){
prime[++tot]=i;
for(int j=i*2;j<=top;j+=i) vis[j]=1;
}
}
void sov(int cas){
int i ;
memset(a,0,sizeof a);memset(b,0,sizeof b);
cin>>m>>n;
for(i=1;i<=tot;i++){
if(m%prime[i]==0){
while(m%prime[i]==0)
a[i]++,m/=prime[i];
}
}
for(i=1;i<=tot;i++){
int t=n;
while(t){
b[i]+=(t/prime[i]);
t/=prime[i];
}
}
int ans=inf;
for(i=1;i<=tot;i++){
if(a[i])
ans=min(ans,b[i]/a[i]);
}
if(ans==0)printf("Case %d:\nImpossible to divide\n",cas);
else printf("Case %d:\n%lld\n",cas,ans);
}
signed main(){
init(1e4);
int tes,cas=0;cin>>tes;
while(tes--) sov(++cas);
}