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 1000000007
using 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;
}