极其简单的题面ioi(听说原题有狗粮？)
题意
求 (frac{1}{x}+frac{1}{y}=frac{1}{n!}) 的正整数解(x,y)的数量. (n<=1e6)
小学奥数？
只记得有求 (frac{1}{x}+frac{1}{y}=frac{1}{z}) 的小学奥数题，我是不是废了...
果然公式推到一半卡了半天qwq.
分析
不知道打表有没有规律，反正上来就推式子了.
不知道怎么换字体...╮(╯﹏╰）╭下面尽量写详细，不注释了.
[egin{eqnarray}
frac{1}{x}+frac{1}{y}=&frac{1}{n!}\
xn!+yn!=&xy\
xy-(x+y)n!=&0\
(n!)^2-(x+y)n!+xy=&(n!)^2\
(n!-x)(n!-y)=&(n!)^2
end{eqnarray}
]
主要是观察(3),发现可以用十字相乘->(4)
然后我们设(a=n!-x,b=n!-y),就有(ab=(n!)^2)
明显当a确定时，能确定b，也能唯一地确定(x,y).
而a的取值个数即((n!)^2)的因子个数.
由唯一分解定理，(n=p_1^{a_1} p_2^{a_2} cdots p_m^{a_m})
所以(n!=p_1^{2a_1}p_2^{2a_2}cdots p_m^{2a_m})
答案即为(n!)的因子个数:((2a_1+1)(2a_2+1)cdots(2a_m+1))
线性筛并记录一个数的最小质因子，暴力分解(n!)即可.
代码
挺好写的(・ω<)
#include <iostream>
#include <cstdio>
#define rg register
using namespace std;
const int mn=1e6+5;
int n,cnt,ans=1,vis[mn],p[mn>>1],c[mn];
int main(){
scanf("%d",&n);
for(rg int i=2;i<=n;++i){
if(!vis[i]) vis[i]=p[++cnt]=i; //vis[i]直接表示i的最小质因子
for(rg int j=1;j<=cnt&&i*p[j]<=n;++j){
vis[i*p[j]]=p[j];
if(!(i%p[j])) break;
}
}
for(rg int i=2;i<=n;++i){int x=i;
while(x!=1) ++c[vis[x]],x/=vis[x]; //分解质因数
}
for(rg int i=2;i<=n;++i) ans=1ll*ans*(c[i]+c[i]+1)%1000000007; //统计答案
printf("%d",ans);
return 0;
}