分析
将方程左边通分
$$
\frac{x+y}{xy}=\frac{1}{n!}
$$
稍加变形得到
$$
xy-n!(x+y)=0
$$
在两边同时加上 $(n!)^2$
$$
(n!)^2-n!(x+y)+xy=(n!)^2
$$
左边可以因式分解，变为
$$
(x-n!)(y-n!)=(n!)^2
$$
设 $a = x - n!$，$b = y - n!$，则 $ab=(n!)^2$。
再设 $n! = p_1^{c_1}\times p_2^{c_2} \times ... \times p_k^{c_k}$，那么有 $(n!)^2=p_1^{2c_1}\times p_2^{2c_2} \times ... \times p_k^{2c_k}$，即
$$
ab=p_1^{2c_1}\times p_2^{2c_2} \times ... \times p_k^{2c_k}
$$
因为 $n!$ 是确定的，所以确定了 $a$、$b$，就能确定 $x$、$y$；而且只要确定了 $a$，就能确定 $b$。
我们知道，$a$ 是 $(n!)^2$ 的约数，那么 $a$ 的个数为：
$$
(2c_1+1)(2c_2+1)...(2c_k+1)
$$
线性筛质数，然后把 $c_i$ 全部计算出来，最后统计答案即可。
关于算 $c_i$，有这样一个公式
$$
c = \sum_{k \geq 0, p^k \leq n} \left\lfloor\frac{n}{p^k}\right\rfloor
$$
代码
#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;
const int MOD=1e9+7;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
return X*w;
}
int n;
int v[10000010];
int prime[10000010];
int s=0;
inline void Get_Prime() {
for (re int i=2;i<=n;i++) {
if (!v[i]) v[i]=i,prime[++s]=i;
for (re int j=1;j<=s;j++) {
if (prime[j]>v[i]||prime[j]>n/i) break;
v[i*prime[j]]=prime[j];
}
}
}
int c[10000010];
mainint main() {
n=read(); Get_Prime();
for (re int i=1;i<=s;i++) {
int P=prime[i];
for (re int j=P;j<=n;j*=P) c[i]+=(n/j);
c[i]%=MOD;
}
int ans=1;
for (re int i=1;i<=s;i++) ans=(ans*(c[i]<<1|1))%MOD;
printf("%lld\n",ans);
return 0;
}
4 条评论
应该可以直接分解吧，不需要筛
您说的对
tql
大佬，强啊。