題目：https://www.lydsy.com/JudgeOnline/problem.php?id=2721

可以知道 x 和 y 一定都大于 n! ，不妨把 y 表示為 n!+t ；

那么 1/x + 1/y = 1/x + 1/(n!+t) = 1/n! ；

整理一下，最終變成：x = (n!)2/t + 1 ；

于是問題轉化為求有多少個 t 讓 x 是整數，也就是?(n!)2 的約數個數；

用質因數分解求，篩素數什么的......

代碼如下：

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int const maxn=1e6+5; int n,pri[maxn],mn[maxn],cnt[maxn],ct; long long ans,mod=1e9+7; void init() {mn[1]=1;// for(int i=1;i<=n;i++){if(!mn[i])pri[++ct]=i,mn[i]=i;for(int j=1;j<=ct&&i*pri[j]<=n;j++){mn[i*pri[j]]=pri[j];if(i%pri[j]==0)break;}} } void cal(int x) {while(x!=1){cnt[mn[x]]++;x/=mn[x];} } int main() {scanf("%d",&n);init();while(n)cal(n),n--;ans=1;for(int i=1;i<=ct;i++)(ans*=(2*cnt[pri[i]]+1))%=mod;printf("%lld",ans);return 0; }

?

轉載于:https://www.cnblogs.com/Zinn/p/9119546.html

總結

以上是生活随笔為你收集整理的bzoj2721樱花——质因数分解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。