洛谷10月月赛R1-T1-一道中档题 Factorial

本文主要是介绍洛谷10月月赛R1-T1-一道中档题 Factorial，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
首先，我们可以这样分解阶乘质因数：

c n t (p) = \sum i = 1 \infty ⌊ n p i ⌋

$cnt(p)=\sum_{i=1}^{\infty} \big\lfloor {\frac n {p^i}}\big\rfloor$
也就是枚举质数一直除，具体原理可以自己想，我不多说。
对于这个题，大家应该有些人做过这个题的简单版本吧：
求n!末尾0的个数。
这个题的做法还是很简单的，用上面那个方法筛出2和5的个数，然后答案就是

min(cnt(2),cnt(5)) $min(cnt(2),cnt(5))$
为什么这么做正确呢？
因为只有2*5能拼出来10。
那么对于这个题也是一样的，我们可以对k进行质因数分解，再用分解出来的质因数去分解n，然后答案就是：

m i n c n t p = 1 (⌊ c n t n ( p r i m e [ p ] ) c n t k ( p r i m e [ p ] ) ⌋)

$min_{p=1}^{cnt}(\big\lfloor{\frac {cntn(prime[p])} {cntk(prime[p])}}\big\rfloor)$
这题如果强化数据到

k<=1016 $k<=10^{16}$ 那么就要这样做
我的另一篇blog
代码：(0ms)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
ll n,k;
ll prime[1000001];
ll e[1000001];
ll ans=1000000000000000LL;
int cnt;
int main(){scanf("%lld %lld",&n,&k);for(ll i=2;i*i<=k;i++){if(k%i==0){prime[++cnt]=i;while(k%i==0){e[cnt]++;k/=i;}}}if(k>1){prime[++cnt]=k;e[cnt]=1;}for(int i=1;i<=cnt;i++){ll now=prime[i];ll num=0;while(now<=n){num+=n/now;now*=prime[i];}ans=min(ans,num/e[i]);}printf("%lld",ans);return 0;
}