题目链接:传送门
题解:
$(1e6)!$ 这种数字,表示都表示不出来,想直接 $O(\sqrt{N})$ 分解质因数这种事情就不要想了。
考虑 $N!$ 的特殊性,这个数字的所有可能包含的质因子,就是 $1 \sim N$ 这些数所包含的质因子。因此,只需要考虑 $1 \sim N$ 这每个数字的质因子即可。
那么,不妨筛出属于 $1 \sim N$ 范围内的所有质数,对于每一个质数 $p$,$1 \sim N$ 中显然有 $\lfloor N/p \rfloor$ 个能够被 $p$ 整除的数字,也就是说 $N!$ 的质因子中,可以确定至少有这么 $\lfloor N/p \rfloor$ 个 $p$。换句话说,产生了 $\lfloor N/p \rfloor$ 的贡献。
然后,我们进一步考虑,$\lfloor N/p \rfloor$ 个能够被 $p$ 整除的数字中,显然还有 $\lfloor N/{p^2} \rfloor$ 个能够被 $p^2$ 整除的数字,这些数字产生进一步产生贡献 $\lfloor N/{p^2} \rfloor$,往后依次类推 $\lfloor N/{p^3} \rfloor, \lfloor N/{p^4} \rfloor, \cdots$。
AC代码:
#include<bits/stdc++.h> #define pb(x) push_back(x) using namespace std; typedef long long ll; int n; const int MAX=1e6; bool noprm[MAX+3]; vector<int> prm; void Erato(int n) { noprm[0]=noprm[1]=1; for(int i=2;i<=n;i++) { if(noprm[i]) continue; prm.pb(i); for(int j=i;j<=n/i;j++) noprm[i*j]=1; } } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>n; Erato(n); for(auto p:prm) { ll cnt=0; for(ll x=p;x<=n;x*=p) cnt+=n/x; if(cnt>0) cout<<p<<' '<<cnt<<'\n'; } }