【数学】樱花

题目

1294. 樱花 - AcWing题库

---

给定一个整数 $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\in \mathbb{Z}^{+}, y\in \mathbb{Z}^{+} \enspace s.t. \enspace \frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$ ，首先通分化简该式：

$$\begin{aligned} \frac{1}{x} + \frac{1}{y} &= \frac{1}{n!} \\ y + x &= \frac{xy}{n!} \\ xn! + yn! &= xy \\ \end{aligned}$$

用 $x$ 表示 $y$ ：

$$\begin{aligned} xn! + yn! &= xy \\ xn! &= xy - yn! \\ xn! &= y(x - n!) \\ y &= \frac{xn!}{x - n!} \end{aligned}$$

此时问题变为：能找到多少个 $x\in\mathbb{Z}^{+} \enspace s.t. \enspace y\in\mathbb{Z}^{+} \Rightarrow \frac{xn!}{x - n!}\in\mathbb{Z}^{+}$ ，变形该式：

$$\begin{aligned} y &= \frac{xn!}{x - n!} \\ &= \frac{((x - n!) + n!)n!}{x - n!} \\ &= \frac{(x - n!)n! + (n!)^2}{x - n!} \\ &= n! + \frac{(n!)^2}{x - n!} \end{aligned}$$

因为 $n \in \{n | 1\le{n}\le10^6, n \in \mathbb{Z}^{+}\}$ ，所以只用保证 $\frac{(n!)^2}{x - n!}$ 即可，也就是要保证 $x-n! \mid (n!)^2$ 。

那么 $x-n!$ 有没有可能小于等于 $0$ 呢？

当 $x-n! \le 0$ 时， $x \le n!$ ，由 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n!} \Rightarrow \frac{1}{y} = \frac{1}{n!} - \frac{1}{x}$ 可知，当 $x \le n!$ 时$\frac{1}{x} \ge \frac{1}{n!} \Rightarrow \frac{1}{n!} - \frac{1}{x} \le 0 \Rightarrow \frac{1}{y} \le 0$ ，与 $y \in \mathbb{Z}^{+}$ 矛盾，所以 $x - n! > 0$ 。

综上：我们需要找到有多少个 $x\in\mathbb{Z}^{+}$ 使得 $x-n! \mid (n!)^2$ ，也就是要算出 $(n!)^2$ 的（正整数）约数个数。

求 $(n!)^2$ 的约数个数可以先用线性筛筛出范围 $[1, n]$ 之间的质数，然后借助勒让德定理求出 $n!$ 的质因数分解中，每个质数的次数（指数）。

根据算术基本定理把 $n!$ 可以质因数分解为：$n! = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}$ ；那么 $(n!)^2$ 就可以分解为：

$$(n!)^2 = p_1^{2\alpha_1} \times p_2^{2\alpha_2} \times \cdots \times p_k^{2\alpha_k}$$

此时 $(n!)^2$ 的约数个数为：

$$f((n!)^2) = \prod_{i=1}^{k}{(2\alpha_i + 1)} = (2\alpha_1 + 1)(2\alpha_2 + 1) \cdots (2\alpha_k + 1)$$

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = (int) 1e6 + 10,  MOD = (int) 1e9 + 7;
    static int[] primes = new int[N];
    static int cnt;
    static boolean[] np = new boolean[N];

    static void sieve(int n) {
        for (int x = 2; x <= n; ++x) {
            if (!np[x]) primes[cnt++] = x;
            for (int i = 0; primes[i] <= n / x; ++i) {
                np[primes[i] * x] = true;
                if (x % primes[i] == 0) break;
            }
        }
    }

    static int count(int n, int p) {
        int res = 0;
        while (n > 0) res += n /= p;
        return res;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); int n = (int) in.nval;
        sieve(n);
        long ans = 1L;
        for (int i = 0; i < cnt; ++i) {
            ans = ans * (2 * count(n, primes[i]) + 1) % MOD;
        }
        System.out.println(ans);
    }
}