看到题目就要开始愉快地推式子
原式 $frac{1}{x}+frac{1}{y}=frac{1}{n!}$
$
ightarrow frac{x+y}{xy}=frac{1}{n!}
ightarrow (x+y)n!=xy
ightarrow xy-(x+y)n!=0$
两边同时加上 $(n!)^2$ 得
$xy-(x+y)n!+(n!)^2=(n!)^2 ightarrow (x-n!)(y-n!)=(n!)^2$
设$a=(x-n!),b=(y-n!)$，则原式化为 $ab=(n!)^2$
如果 a 确定了，那么 b 也确定了，那么 x,y 也都确定了
所以就变成了求 a 的取值方案数
设$z=(n!)^2$
运用唯一分解定理把$z$分解成几个质数的乘积
$z=p_1^{k_1}p_2^{k_2}...p_n^{k_n}$
a可以在每个质数中取 0 到 k1 个作为质因子，那么每个质数有 $k_i+1$ 种取法
根据乘法原理，共有 $(k_1+1)(k_2+1)...(k_n+1)$ 种取法
所以答案就是这个
把阶乘分解就只要把 1 到 n 每个数都分解一遍，复杂度O(nlogn)
分解一个数的质因子都会吧..就不讲了
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<iostream> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7,mo=1e9+7; int n,cnt[N],ans=1;//cnt存 (n!)^2 的质因子数量 int pri[N],tot,p[N];//p存每个数最小的质因子 bool not_pri[N]; void pre() { not_pri[1]=1; p[1]=1; for(int i=2;i<=n;i++) { if(!not_pri[i]) { pri[++tot]=i; p[i]=i; } for(int j=1;j<=tot;j++) { ll g=pri[j]*i; if(g>n) break; not_pri[g]=1; p[g]=pri[j]; if(!(i%pri[j])) break; } } } int main() { n=read(); pre(); for(int i=1;i<=n;i++) { int t=i; while(t!=1) cnt[p[t]]++,t/=p[t];//分解质因子 } for(int i=1;i<=tot;i++) ans=1ll*ans*(cnt[pri[i]]*2+1)%mo;//记得cnt要乘2加1 printf("%d",ans); return 0; }