题目描述

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

输入格式

一个整数 $n$

输出格式

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

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

数据范围

$1\leq n \leq10^6$

输入样例

2

输出样例

3

样例解释

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

分析

对$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$进行等价变形:

左边进行通分: $\frac{x+y}{xy}=\frac{1}{n!}$

化简:
$(x+y)n! = xy$
$xn!+yn! = xy$
$xn! = y(x-n!)$
$y = \frac{xn!}{x-n!} = \frac{(x-n!+n!)n!}{x-n!} = 1 + \frac{n!^2}{x-n!}$

这样只要我们保证$\frac{n!^2}{x-n!}$是正整数就可以了，可以看到分子肯定是正整数，那么分母有没有可能小于0呢。
答案是不可能的。

因为$\frac{1}{y} = \frac{1}{n!}-\frac{1}{x}$ , 如果$x < n!$那么 $y$ 就会是负数。

消除了分母为负数的疑虑，那么我们怎么保证$\frac{n!^2}{x-n!}$是正整数呢，显然只要 $(x - n!) | (n!^2)$

问题就转化为求 $n!^2$ 的约数个数

由算术基本定理得：$n!^2$可分解为$p1^{2k1}+p2^{2k2}+p3^{2k3}......+pn^{2kn}$ ， 答案就是$(2k1+1)(2k2+1)…(2kn+1)$

C++代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10, mod = 1e9 + 7;

int primes[N], cnt;
bool st[N];

void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;

    init(n);

    int res = 1;
    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        int s = 0;
        for (int j = n; j; j /= p) s += j/p;
        res = (LL)res * (2 * s + 1) % mod;
    }

    cout << res << endl;
    return 0;
}