数学之约数个数定理-阶乘约数

数学之约数个数定理-阶乘约数

引用

CSDN

1.

https://blog.csdn.net/2301_81354767/article/details/146122005

在数学和编程领域，计算阶乘的约数个数是一个经典问题。本文将详细介绍如何通过质因数分解的方法来解决这个问题，并给出具体的代码实现。

定义阶乘 n! = 1 × 2 × 3 × ⋯ × n。请问 100!（100的阶乘）有多少个正约数。

我们需要计算 100! 的正约数的个数。阶乘 100! 的定义是：
100! = 1 × 2 × 3 × ⋯ × 100

直接计算 100! 的值是不现实的，因为它是一个非常大的数。因此，我们需要找到一种间接的方法来计算其正约数的个数。

为什么选择质因数分解？

1. 正约数的性质

• 一个数的正约数的个数与其质因数分解密切相关。
• 如果一个数的质因数分解为：
  [n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}]
  那么它的正约数的个数为：
  [(e_1 + 1) \times (e_2 + 1) \times \cdots \times (e_k + 1)]
• 因此，计算正约数的个数可以转化为计算质因数的指数。

2. 阶乘的质因数分解

• 阶乘 n! 的质因数分解可以通过对 1 到 n 的每个数进行质因数分解，然后统计每个质数的总指数。
• 例如，10! 的质因数分解为：
  [10! = 2^8 \times 3^4 \times 5^2 \times 7^1]
  其正约数的个数为：
  [(8+1) \times (4+1) \times (2+1) \times (1+1) = 270]

3. 方法的可行性

• 质因数分解是数论中的经典问题，有成熟的算法（如试除法、筛法等）可以高效实现。
• 对于 n=100，质因数分解的计算量是可以接受的。

解题代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int a[N]; // 数组 a 用于存储每个质数的指数

// 质因数分解函数
void f(int n)
{
  for (int i = 2; i <= n / i; i++) // 从 2 开始枚举可能的质因数
  {
    if (n % i) continue; // 如果 i 不是 n 的因数，跳过
    while (n % i == 0) n /= i, a[i]++; // 统计质因数 i 的指数
  }
  if (n > 1) a[n]++; // 如果 n 是质数，直接统计
}

int main()
{
  int n = 100; // 计算 100! 的正约数个数
  for (int i = 1; i <= n; i++) f(i); // 对 1 到 100 的每个数进行质因数分解
  ll ans = 1; // 初始化答案为 1
  for (int i = 1; i <= n; i++)
  {
    ans = ans * (a[i] + 1); // 计算正约数的个数
  }
  cout << ans << '\n'; // 输出结果
  return 0;
}

为什么正约数个数是 ((e_1+1) \times (e_2+1) \times \cdots \times (e_k+1)) 相乘而不是相加？

1. 质因数分解与约数的关系

• 假设一个数 n 的质因数分解为：
  [n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}]
  其中 (p_1, p_2, \ldots, p_k) 是质数，(e_1, e_2, \ldots, e_k) 是它们的指数。

2. 约数的形式

• 任何一个约数 d 都可以表示为：
  [d = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}]
  其中 (0 \leq a_i \leq e_i)。

3. 约数的个数

• 对于每个质因数 (p_i)，指数 (a_i) 有 (e_i+1) 种选择（从 0 到 (e_i)）。
• 因此，总的约数个数是每个质因数的选择数的乘积：
  [(e_1+1) \times (e_2+1) \times \cdots \times (e_k+1)]

4. 为什么是相乘而不是相加？

• 如果我们将每个质因数的选择数相加，得到的是所有可能的指数的总和，而不是约数的个数。
• 相乘是因为每个质因数的选择是独立的，我们需要考虑所有可能的组合。

示例

假设 n = 12，其质因数分解为：
[12 = 2^2 \times 3^1]

根据公式，正约数的个数为：
[(2+1) \times (1+1) = 6]

实际上，12 的正约数为：1, 2, 3, 4, 6, 12，共 6 个。

代码逻辑回顾（计算 10! 的正约数个数）

1. 数组 a[N]： 用于存储每个质数的指数。
2. 函数 f(n)： 对整数 n 进行质因数分解，并更新数组 a。
3. 主函数：

• 对 1 到 10 的每个数调用 f(n)，更新数组 a。
• 根据数组 a 计算正约数的个数，公式为：
  [ans = (a[2]+1) \times (a[3]+1) \times \cdots \times (a[7]+1)]

初始化

• 数组 a[N] 初始化为全 0。
• 变量 ans 初始化为 1。

逐步调用 f(n) 并更新数组 a

1. 调用 f(1)
2. 调用 f(2)
3. 调用 f(3)
4. 调用 f(4)
5. 调用 f(5)
6. 调用 f(6)
   
7. 调用 f(7)
8. 调用 f(8)
   
9. 调用 f(9)
10. 调用 f(10)

计算正约数的个数

根据数组 a 的最终状态：
a = [0, 0, 8, 4, 0, 2, 0, 1, 0, 0, 0]

其中：

• a[2] = 8（质数 2 的指数）
• a[3] = 4（质数 3 的指数）
• a[5] = 2（质数 5 的指数）
• a[7] = 1（质数 7 的指数）

根据正约数公式：
ans = (a[2]+1) × (a[3]+1) × (a[5]+1) × (a[7]+1)

代入数值：
ans = (8+1) × (4+1) × (2+1) × (1+1)

计算：
ans = 9 × 5 × 3 × 2 = 270

最终结果

10! 的正约数的个数为 270。