樱花

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

输入格式

一个整数 $n$。

输出格式

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

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

数据范围

$ 1 \leq n \leq {10}^6$

输入样例：

2

输出样例：

3

样例解释

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

解题思路

\begin{align*}
\frac{1}{x} + \frac{1}{y} &= \frac{1}{n!} \\\\
\frac{x+y}{xy} &= \frac{1}{n!} \\\\
{x} \cdot {n!} + y \cdot {n!} &= x \cdot y
\end{align*}

　　可以发现有两个自变量，因此可以通过枚举来固定$x$然后通过$x$与$y$的关系来得到满足条件的$y$。其中$y$关于$x$的函数为$y = \dfrac{x \cdot {n!}}{x - {n!}}$。

　　现在问题就变成了有多少个正整数$x$使得$\dfrac{x \cdot {n!}}{x - {n!}}$是一个正整数。由于分子分母同时含有$x$不方便处理，因此把分子的$x$去掉。$$y = \dfrac{x \cdot {n!}}{x - {n!}} = \frac{(x - {n!} + {n!}) \cdot {n!}}{x - {n!}} = {n!} + \frac{(n!)^2}{x - {n!}}$$

　　由于$n!$必然是一个正整数，因此问题又变成了有多少个正整数$x$使得$\dfrac{(n!)^2}{x - {n!}}$是一个正整数。$x$一定正整数，但分母的$x - {n!}$不一定是正整数，事实上根据$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$得到$\frac{1}{y}=\frac{1}{n!} - \frac{1}{x}$，由于$x$和$y$均要满足正整数的条件，因此$x$必然要满足$x > {n!}$，因此$x - {n!} > 0$。因此问题就等价于有多少个正整数$x$使得$x - {n!}$是$(n!)^2$的约数，等价于就是问$(n!)^2$的约数个数。其中如果一个数$N = P_{1}^{\alpha_{1}} \cdot P_{2}^{\alpha_{2}} \cdot \cdots \cdot P_{n}^{\alpha_{n}}$，那么约数的个数为$\left( {\alpha_{1} + 1} \right) \cdot \left( {\alpha_{2} + 1} \right) \cdot \cdots \cdot \left( {\alpha_{n} + 1} \right)$。

　　AC代码如下：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 1e6 + 10, mod = 1e9 + 7;
 5 
 6 int primes[N], cnt;
 7 bool vis[N];
 8 
 9 void get_prime(int n) {
10     for (int i = 2; i <= n; i++) {
11         if (!vis[i]) primes[cnt++] = i;
12         for (int j = 0; primes[j] <= n / i; j++) {
13             vis[primes[j] * i] = true;
14             if (i % primes[j] == 0) break;
15         }
16     }
17 }
18 
19 int main() {
20     int n;
21     scanf("%d", &n);
22     get_prime(n);
23     int ret = 1;
24     for (int i = 0; i < cnt; i++) {
25         int p = primes[i], s = 0;
26         for (int j = n; j; j /= p) {
27             s += j / p;
28         }
29         ret = ret * (2ll * s + 1) % mod;
30     }
31     printf("%d", ret);
32     
33     return 0;
34 }

参考资料

　　AcWing 1294. 樱花（算法提高课）：https://www.acwing.com/video/691/