Luogu P1445[Violet]樱花/P4167 [Violet]樱花

Luogu P1445[Violet]樱花/P4167 [Violet]樱花

真·双倍经验
化简原式：
\[\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\]
\[\frac{xy}{x+y}=n!\]
\[xy=n!(x+y)\]
\[-n!(x+y)+xy=0\]
\[(n!x+n!y)-xy=0\]
\[(n!)^2+(n!x+n!y)-xy=(n!)^2\]
\[(x-n!)(y-n!)=(n!)^2\]
所以\((x-n!)\)就是\((n!)^2\)的一个因子。
又因为\((x-n!)\)的数量和\(x\)相等，那么解的个数就是\((n!)^2\)的因数个数。

#include<bits/stdc++.h>
#define N 1000010
#define MOD 1000000007using namespace std;int n,cnt;
int pri[N];
long long ans=1;
bool vis[N];void Read() {scanf("%d",&n);return;
}void EulerSieve(int x) {for(int i=2;i<=x;i++) {if(!vis[i]) {pri[++cnt]=i;}for(int j=1;j<=cnt;j++) {if(i*pri[j]>x) {break;}else {vis[i*pri[j]]=1;}if(!(i%pri[j])) {break;}}}return;
}int Factor(int k,int p) {if(k<p) {return 0;}else {return k/p+Factor(k/p,p);}
}void Solve() {for(int i=1;i<=cnt;i++) {ans*=Factor(n,pri[i])*2+1;ans%=MOD;}printf("%lld",ans);return;
}int main()
{Read();EulerSieve(n);Solve();return 0;
}