1624：樱花

题目描述

求不定方程：

的正整数解 $(x,y)$ 的数目。

输入格式

一个整数 $n$。

输出格式

一个整数，表示有多少对 $(x,y)$ 满足题意。答案对 $10^9+7$ 取模。

样例

样例输入 #1

2

样例输出 #1

3

样例解释 #1

• $n=2$，$n! = 2$。
• 方程：$\frac{1}{x} + \frac{1}{y} = \frac{1}{2}$。
• 正整数解有：
  1. $(x,y) = (3,6)$
  2. $(x,y) = (4,4)$
  3. $(x,y) = (6,3)$
• 共 $3$ 对。

数据范围

• 对于 $30\%$ 的数据，$n \le 100$；
• 对于全部数据，$1 \le n \le 10^6$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题需要将方程变形。由 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$，通分得 $\frac{x+y}{xy} = \frac{1}{n!}$，即 $n!(x+y) = xy$。移项：$xy - n!x - n!y = 0$，配方：$(x - n!)(y - n!) = (n!)^2$。

令 $a = x - n!$, $b = y - n!$，则 $ab = (n!)^2$。由于 $x, y$ 是正整数，$a, b$ 是整数且 $a > -n!$, $b > -n!$。但 $x = a + n! > 0$ 且 $y = b + n! > 0$，所以 $a, b$ 可以取任意整数使得 $ab = (n!)^2$ 且 $a > -n!$, $b > -n!$。实际上，由于 $n! > 0$，$a$ 和 $b$ 同号，且 $a, b$ 可以是正数或负数，但 $x, y$ 为正整数，所以 $a > -n!$，即 $a$ 最小可取 $-n!+1$，此时 $x=1$。但更方便的是，我们只关心正整数解，所以 $x, y$ 为正整数，即 $a > -n!$ 且 $b > -n!$。由于 $ab = (n!)^2 > 0$，$a$ 和 $b$ 同号，且 $a, b$ 可以是正数或负数。

但 $a$ 和 $b$ 是 $(n!)^2$ 的因子。设 $(n!)^2$ 的因子个数为 $d$，则有序对 $(a,b)$ 有 $d$ 组（包括正负因子）。但需要满足 $x, y$ 为正整数，即 $a > -n!$ 且 $b > -n!$。由于 $ab = (n!)^2$，如果 $a$ 是负数且绝对值大于 $n!$，则 $b = (n!)^2 / a$ 是负数且绝对值小于 $n!$，那么 $b > -n!$ 可能成立（因为 $b$ 是负数且绝对值小于 $n!$，所以 $b > -n!$）。但 $a < -n!$ 时，$x = a + n! < 0$，不是正整数。所以必须 $a \ge -n! + 1$。同理 $b \ge -n! + 1$。

然而，我们可以直接考虑正整数解。由于 $x, y$ 对称，我们只需求出正整数解的数量（包括 $x=y$ 和 $x \ne y$ 但对称）。由 $(x - n!)(y - n!) = (n!)^2$，令 $X = x - n!$, $Y = y - n!$，则 $XY = (n!)^2$。$x, y$ 为正整数当且仅当 $X > -n!$, $Y > -n!$。由于 $X$ 和 $Y$ 同号，且乘积为正，它们要么都是正数，要么都是负数且绝对值至少为 $1$。但 $X > -n!$ 且 $Y > -n!$，如果 $X$ 是负数，则 $X \ge -n!+1$，即 $X \ge -(n!-1)$。同理 $Y$。但 $XY = (n!)^2$，如果 $X$ 是负数，则 $Y$ 也是负数，且 $|X| \cdot |Y| = (n!)^2$。由于 $|X| \le n!-1$，则 $|Y| \ge \frac{(n!)^2}{n!-1} > n!$，所以 $Y < -n!$，不满足 $Y > -n!$。因此 $X$ 和 $Y$ 不能同时为负数。所以 $X$ 和 $Y$ 必须都是正数。

因此，问题转化为求 $(n!)^2$ 的正因子个数 $d$，则有序正整数解 $(x,y)$ 的数目就是 $d$（因为每个正因子 $X$ 对应一个 $Y = (n!)^2 / X$，且 $x = X + n! > 0$, $y = Y + n! > 0$）。注意 $x$ 和 $y$ 对称，但有序对 $(x,y)$ 包括 $(a,b)$ 和 $(b,a)$。

所以答案就是 $(n!)^2$ 的约数个数。设 $n! = \prod p_i^{e_i}$，则 $(n!)^2 = \prod p_i^{2e_i}$，约数个数 $d = \prod (2e_i + 1)$。

因此，我们需要对 $n!$ 进行质因数分解，求出每个质数 $p$ 的指数 $e_p$，然后计算 $\prod (2e_p + 1) \bmod (10^9+7)$。

由于 $n \le 10^6$，可以用线性筛预处理所有质数，然后对每个质数 $p$ 计算 $e_p = \sum_{k=1}^{\infty} \lfloor n / p^k \rfloor$（勒让德公式）。注意中间结果可能很大，需要取模。