就是化柿子
我们求
\[\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}
\]
\]
的正整数解的个数
喜闻乐见的化柿子了
\[\frac{x+y}{xy}=\frac{1}{n!}
\]
\]
\[xy=xn!+yn!
\]
\]
\[xy-xn!=yn!
\]
\]
\[x=\frac{yn!}{y-n!}
\]
\]
所以这里的\(y\)显然是要大于\(n!\)的
设\(y=n!+c\)
那么
\[x=\frac{n!(n!+c)}{n!+c-n!}=\frac{n!(n!+c)}{c}=\frac{(n!)^2+n!c}{c}
\]
\]
\[x=\frac{(n!)^2}{c}+\frac{n!c}{c}=\frac{(n!)^2}{c}+n!
\]
\]
因为\(x\)也是正整数，就是说现在\(c\)是\((n!)^2\)的约数
问题也就变成了求\(d((n!)^2)=\sum_{i|n}1\)
之后线筛一下暴力分解质因数就好了
代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define re register
#define maxn 1000005
const LL mod=1e9+7;
inline int read()
{
char c=getchar();
int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x;
}
int n;
int f[maxn],p[maxn>>1];
int to[maxn],num[maxn>>1];
int main()
{
scanf("%d",&n);
f[1]=1;
for(re int i=2;i<=n;i++)
{
if(!f[i]) p[++p[0]]=i,to[i]=p[0],num[to[i]]++;
for(re int j=1;j<=p[0]&&p[j]*i<=n;j++)
{
f[p[j]*i]=1;
if(i%p[j]==0) break;
}
}
for(re int i=2;i<=n;i++)
if(f[i])
{
int mid=i;
int up=std::sqrt(i);
for(re int j=1;j<=p[0]&&p[j]<=up;j++)
{
while(mid%p[j]==0) num[j]++,mid/=p[j];
if(mid==1) break;
}
if(mid!=1) num[to[mid]]++;
}
LL ans=1;
for(re int i=1;i<=p[0];i++)
ans=(ans*(2*num[i]+1))%mod;
std::cout<<(ans%mod);
return 0;
}