本文主要是介绍hihocoder 1789 阶乘问题（数论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://hihocoder.com/problemset/problem/1789
求一个最大的整数 m，使得 k^m 是 n! 的约数
我们可以看成是k^m*x=n！，且m为最大了，那意味着x不能拆成k*y了，所以我们就只要求n！中每个乘数拆成若干个质数相乘，然后求这些质数能组成多少个k。
因为是质数，所以都是互不干扰的，不存在重复的问题。
因此我们可以先求k是由哪些质数相乘得到。然后求每个质数在n！里有多少个，最终取最小值。
例如 n=8 k=6
那么8！=2*3*2*2*5*2*3*7*2*2*2*2=2*3*4*5*6*7*8；
6=2*3；
那么我们可以得到8！中的2有8/1=8个，3有2/1=2个，那么我们的答案就是2
#include<bits/stdc++.h>
using namespace std;
long long n,k;
long long zs[100006];
bool vis[100086];
int main(){int js=0;memset(vis,0,sizeof(vis));for(long long i=2;i<=100010;i++){if(vis[i]==0){zs[js++]=i;for(long long j=i*i;j<=100010;j+=i){vis[j]=1;}}}while(cin>>n>>k){long long lss=k;int zz=0;int zz1=0;long long yz[100006];long long sl[100006];while(lss<=zs[js-1]&&zz<js&&lss>1){int jj=0;while(lss%zs[zz]==0&&lss>1){lss/=zs[zz];jj++;}if(jj!=0){yz[zz1++]=zs[zz];sl[zz1-1]=jj;}zz++;}if(lss>1){yz[zz1]=lss;sl[zz1++]=1;}long long mi=99999999999;for(int i=0;i<zz1;i++){long long lb=yz[i];long long zp=lb;long long jss=0;while(n/zp>=1){jss+=n/zp;zp*=lb; }mi=min(mi,jss/sl[i]);}cout<<mi<<endl;}return 0;
}
这篇关于hihocoder 1789 阶乘问题（数论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
