---
title: "樱花"
created: 2025-11-28
tags:
  - 算法
---

# 樱花

## 题目 [樱花](https://www.cnblogs.com/jungu/p/13387650.html)

给出一个整数ｎ，求有多少个正整数对（x, y）满足$1/x + 1/y = 1/n!$

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

## 思路分析

![[image-3ef6971b.png]]

![[image-84dc921a.png]]

约数个数：

$N = (p1^{x1})(p2^{x2})(p3^{x3})…(pk^{xk})$

N的约数个数：$(x1+1)(x2+1)(x3+1)…(xk+1)$

主要是这个公式推导 变成求$(n!)^2$的个数

就算推导出来了

怎么理解

![[image-e2c80812.png]]

在数论中，当你有一个整数 n!，这个数可以被分解为其质因数的乘积。具体地说，任何正整数 N 都可以被唯一地表示为有限个质数的乘积，即：

![[image-bfc86f4c.png]]

其中，每个 pi 是一个质数，而每个 li 是对应质数的指数。对于 n!（n 的阶乘），这种分解特别有用，因为它让我们可以很方便地计算某个质数在
n! 中出现了多少次。

例如，如果 n=5，那么：

$5!=5⋅4⋅3⋅2⋅1=2^3⋅3^1⋅5^1$

（又是倍数思想吗）

这里，2 是基数，它出现了 3 次（即指数为 3），3 是基数，出现了 1 次，5 也是基数，出现了 1 次。这个质因数分解直接告诉我们 n!
的每个质因数的精确次数，而不需要我们一一枚举每个数来检查它是否是 n! 的因子。

在给定的问题中，我们感兴趣的是找出满足等式

![[image-59de4207.png]]

的正整数对 (x,y) 的数量。我们首先理解 n! 作为分母时，它的质因数分解意味着每个质因数 pi 必须同时出现在 x 和 y 的质因数分解中。

以

![[image-02f600e6.png]]

的形式，我们可以观察到等式

![[image-4c9dbcd3.png]]

实际上表示 x 和 y 是$n!^2$ 的约数对，这是因为：

![[image-a9d1db02.png]]

由于 x 和 y 都是 n! 的倍数，我们可以推断，每对 x 和 y 都对应 n! 的一个约数 d。换句话说，对于 n! 的每个约数 d，都存在一对
(x,y) 使得

![[image-89d60268.png]]

因此，我们只需要计算 n! 的约数总数，就可以知道满足条件的 (x,y) 对的总数。

由于每个质因数 pi 的指数是 li，n! 的每个约数都可以表示为 $p1^{a1}⋅p2^{a2}⋅…⋅p\_k^{ak}$，其中
ai 是从 0 到 li 的整数。这意味着 pi 贡献了 li+1 种可能的指数。因此，约数的总数是所有这些可能性的乘积，即：

![[image-a9299440.png]]

要计算满足条件的 (x,y) 对的总数，我们需要找到每个 li，这就需要先找出 n 以下的所有质数，然后对于每个质数 pi，计算它在 n!
中作为因子的次数 li。这可以通过不断除以 pi 并累加得到。每个 li 加一后再相乘，就得到了 n! 的约数总数。

最后，由于 x 和 y 可以互换，每个约数对

![[image-e619f73e.png]]

都会被算两次，所以我们需要将最终的约数总数除以 2。

好了 其实就是n! 是$1\*2\*3\*4……n$

然后把这里面的非质因数项合并到质因数里面去

4就是2个2 那么2出现三次

处理好了这个合并

公式就变成了$2^3\*3^k……$这样式子

显然就是约数之和的模板了 把所有项的(指数+1)累乘起来

## 代码实现

```cpp
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 10;

vector<int> get_primes(int n) {
    vector<bool> is_prime(n + 1, true);
    vector<int> primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = 2 * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

int main() {
    int n;
    cin >> n;
    vector<int> primes = get_primes(n);

    long long result = 1;
    // 遍历所有质数，并计算n!中每个质数的指数
    for (int p : primes) {
        long long count = 0; // 存储当前质数的指数
        long long temp = n;
        // 计算n!中质数p的指数
        while (temp) {
            count += temp / p; // 累加指数
            temp /= p; // 除以质数p，继续计算
        }
        result = result * (count + 1) % MOD;
    }

    cout << result << endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[基础约数|基础约数]] 🏠 [[00-刷题理模型]] ➡️ [[欧几里得算法（辗转相除）|欧几里得算法（辗转相除）]]