原文地址
分析
题目要求求出不定方程:\(\dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n}\)的解\((x,y为未知数,n为给定的常数)\)。
观察原式可以发现\(x\)和\(y\)必定大于\(n!\),那么不妨令
\(y=n!+k,(k\in Z^*)\)
则原式变为
\(\dfrac{1}{x}+ \dfrac{1}{n!+k}= \dfrac{1}{n!}\)
变形之后得到
\(x=\dfrac{n!*(n!+k)}{k}\)
进一步得到
\(x=\dfrac{(n!)^2}{k}+n!\)
分析到这里我们就将其转化为\(x\)关于\(k\)的一个方程,而我们要求得数对\((x,y)\)的个数也就是方程解的个数。
因为\(x\)是正整数,所以\(\dfrac{(n!)^2}{k}+k\)也为正整数。
由于\(k\in Z^{ * }\),所以\((n!)^2\)必须能够被\(k\)整除,换句话说就是\(k\)是\((n!)^2\)的约数。
所以这道题的实质是:
\(求n!^2的所有正约数的个数\)
约数个数
根据算数基本定理得正整数\(N\)能被唯一分解为
\(N=p_{1}^{c_1}*p_{2}^{c_2}*p_{3}^{c_3}*\cdots*p_{n}^{c_n}\)
其中\(c\)为任意常数,\(p\)为质数,且满足\(p_1\leq p_2\leq p_3\leq\cdots p_n\)。
则\(N\)的正约数个数为
\((c_1+1)*(c_2+1)*(c_3+1)\cdots*(c_n+1)= \prod_{i=1}^n (c_i+1)\)
为了提高效率,我们采用线性筛素数的方法,先找出\(n!\)的质因子,再通过分解质因数的方法找出所有的\(c_i\)即可。
注意我们这里只是找出了\(n!\)的所有的\(c_i\),而题目要求的是\((n!)^2\)的约数个数,所以统计时一定要乘\(2\)。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000010, mod = 1e9 + 7;
int primes[N], cnt;
int sum[N];
bool st[N];
int n;
void init(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
int main()
{
cin >> n;
init(n);
for (int i = 0; i < cnt; i ++ )
for (LL j = primes[i]; j <= n; j *= primes[i])
sum[i] += n / j;
LL res = 1;
for (int i = 0; i < cnt; i ++ )
res = res * (2 * sum[i] + 1) % mod;
cout << res << endl;
return 0;
}