题目描述
给定 \(n(1\leq n\leq 10^6)\),求有多少对整数 \((x,y)\) 满足 \(\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}\),答案对 \(10^9+7\) 取模。
分析
设 \(z=n!,y=z+d\)。
\[\begin{aligned}&\frac{1}{x}+\frac{1}{y}\\=&\frac{1}{x}+\frac{1}{z+d}\\=&\frac{x+z+d}{x(z+d)}\\=&\frac{1}{z}\end{aligned} \]则 \(x=\frac{z^2}{d}+z\),求 \(z^2\) 的因子数即可。
设 \(z=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}\),因子数为 \(ans=(1+p_1)(1+p_2)\cdots(1+p_k)\)。
\(z^2=p_1^{2c_1}p_2^{2c_2}\cdots p_k^{2c_k}\),答案为 \(ans=(1+2p_1)(1+2p_2)\cdots(1+2p_k)\)。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;
int prime[N+10],vis[N+10],cnt;
void init()
{
for(int i=2;i<=N;i++)
{
if(!vis[i])
prime[++cnt]=i;
for(int j=1;i*prime[j]<=N&&j<=cnt;j++)
{
vis[i*prime[j]]=1;
if(i%prime[j]==0)
break;
}
}
}
long long num[N+10];
int main()
{
init();
int n;
cin>>n;
for(int i=1;i<=cnt;i++)
{
int temp=n;
while(temp)
{
num[i]=num[i]+temp/prime[i];
temp=temp/prime[i];
}
}
long long ans=1;
for(int i=1;i<=cnt;i++)
ans=ans*(2*num[i]%mod+1)%mod;
cout<<ans<<endl;
return 0;
}