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

2025/3/9 17:24:21 来源：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. 正约数的性质

一个数的正约数的个数与其质因数分解密切相关。
如果一个数的质因数分解为：

那么它的正约数的个数为：
因此，计算正约数的个数可以转化为计算质因数的指数。

2. 阶乘的质因数分解

阶乘 n!的质因数分解可以通过对 1 到 n 的每个数进行质因数分解，然后统计每个质数的总指数。
例如，10! 的质因数分解为：

其正约数的个数为：

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; // 初始化答案为 1for(int i=1;i<=n;i++){ans=ans*(a[i]+1); // 计算正约数的个数}cout<<ans<<'\n'; // 输出结果return 0;
}

为什么正约数个数是 (e1+1)×(e2+1)×⋯×(ek+1)相乘而不是相加？

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

假设一个数 n 的质因数分解为：
其中 p1,p2,…,pk是质数，e1,e2,…,ek是它们的指数。

2. 约数的形式

任何一个约数 d 都可以表示为：

3. 约数的个数

对于每个质因数 pi，指数 ai有 ei+1种选择（从 0 到 ei）。
因此，总的约数个数是每个质因数的选择数的乘积：

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

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

示例

假设 n=12，其质因数分解为：

根据公式，正约数的个数为：

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

代码逻辑回顾(计算 10!的正约数个数)

数组 a[N]：用于存储每个质数的指数。
函数 f(n)：对整数 n 进行质因数分解，并更新数组 a。
主函数：
- 对 1 到 10 的每个数调用 f(n)，更新数组 a。
- 根据数组 a 计算正约数的个数，公式为：
  ans=(a[2]+1)×(a[3]+1)×⋯×(a[7]+1)