樱花

题目 樱花

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

答案对\(10^9+7\)取模

思路分析

image-3ef6971b image-84dc921a

约数个数：

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

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

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

就算推导出来了

怎么理解

image-e2c80812

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

image-bfc86f4c

其中，每个 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

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

以

image-02f600e6

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

image-4c9dbcd3

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

image-a9d1db02

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

image-89d60268

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

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

image-a9299440

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

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

image-e619f73e

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

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

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

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

处理好了这个合并

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

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

代码实现

#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-刷题理模型 ➡️ 欧几里得算法（辗转相除）