<—点个赞吧QwQ

宣传一下算法提高课整理

给定一个整数 $n$，求有多少正整数数对 $(x,y)$ 满足 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$。

输入格式

一个整数 $n$。

输出格式

一个整数，表示满足条件的数对数量。

答案对 $10^9+7$ 取模。

数据范围

$1 \le n \le 10^6$

输入样例：

2

输出样例：

3

样例解释

共有三个数对 $(x,y)$ 满足条件，分别是 $(3,6),(4,4),(6,3)$。

思路

这个需要推式子。
首先，根据我们已知的小学数学，可以得出$x,y>n!$
不妨设$y=n!+k$

$\dfrac{1}{x}+\dfrac{1}{n!+k}=\dfrac{1}{n!}$

将两边同分得：

$n! \times (n!+k) + n! \times x=x \times (n! + k)$

整理得：
$x = \dfrac{{(n!)}^2}{k}+n!$

$\because x,y\in N^*$

$\therefore k|{(n!)^2}$

所以就变成了求${(n!)}^2$的约数个数了。

即$n!$的每个约数个数$\times 2$。
所以就要用到阶乘分解了。
然后。。。然后就没有然后了。

代码

#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1000010,MOD = 1e9 + 7;
int n;
int primes[N],cnt;
bool is_prime[N];
void get_primes (int n) {
    memset (is_prime,true,sizeof (is_prime));
    is_prime[1] = false;
    for (int i = 2;i <= n;i++) {
        if (is_prime[i]) primes[++cnt] = i;
        for (int j = 1;primes[j] * i <= n;j++) {
            is_prime[primes[j] * i] = false;
            if (i % primes[j] == 0) break;
        }
    }
}
int main () {
    cin >> n;
    get_primes (n);
    LL ans = 1;
    for (int i = 2;i <= n;i++) {
        if (!is_prime[i]) continue;
        LL res = 0;
        for (LL j = i;j <= n;j *= i) res += n / j;
        ans = ans * (res * 2 + 1) % MOD;
    }
    cout << ans << endl;
    return 0;
}