P1445 [Violet] 樱花

算法

数学（素数筛，因子个数）

思路

对于原式做如下推导：

\large \begin{aligned} \frac{1}{x} + \frac{1}{y} &= \frac{1}{n!} \\ \frac{x + y}{xy} &= \frac{1}{n!} \\ n! \cdot (x + y) &= xy \\ n! \cdot x + n! \cdot y - xy &= 0 \\ xy - n! \cdot x - n! \cdot y &= 0 \end{aligned}

由上式联想到：

\large (a - x) (b - x) \to ab - ax - bx - X^2

比较两式，发现缺少 $(n!)^2$ 项。加上 $(n!)^2$ ，得：

\large \begin{aligned} (x - n!)(y - n!) = (n!)^2 \end{aligned}

由于等式左边是乘积的形式，所以 $(x - n!)$ 和 $(y - n!)$ 必定是 $(n!)^2$ 的一对因子。将 $n$ 质因数分解：

\large n = \prod_{i = 0}^{k} p_i^{\alpha_{i}}

对于 $n!$ 的因子个数 $sum_{1}$ 有：

sum_{1} = \prod_{i=0}^{k} (\alpha_{i}+ 1)

而 $(n!)^2$ 的因子个数 $sum_{2}$ 为：

sum_{2} = \prod_{i = 0}^{k} (\alpha_{1} \cdot 2 + 1)

根据乘法原理，最后的答案为所有 $sum_{2}$ 的乘积。

代码

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
constexpr int MOD = 1e9 + 7;
6

7
inline vector<int> GetPrimes(int Limit) {
8
  vector<int> primes;
9
  vector<bool> mark(Limit + 1);
10

11
  for (int i = 2; i <= Limit; i ++) {
12
    if (mark[i] == false) {
13
      primes.emplace_back(i);
14
    }
15

16
    for (int j = 0; i * primes[j] <= Limit; j ++) {
17
      mark[i * primes[j]] = true;
18
      if (i % primes[j] == 0) {
19
        break;
20
      }
21
    }
22
  }
23

24
  return primes;
25
}
26

27
int main() {
28
  ios::sync_with_stdio(false);
29
  cin.tie(nullptr);
30
  cout.tie(nullptr);
31

32
  int n;
33
  cin >> n;
34

35
  vector<int> primes = GetPrimes(n);
36
  // * 注意由于是连乘，所以 answer 的初始值为 1.
37
  long long answer = 1;
38

39
  for (auto&& p : primes) {
40
    int alpha = 0, number = n;
41

42
    while (number) {
43
      alpha += number / p;
44
      number /= p;
45
    }
46

47
    answer = (answer * (alpha + alpha + 1) % MOD) % MOD;
48
  }
49

50
  cout << answer % MOD << '\n';
51

52
  return 0;
53
}