阶乘约数（唯一分解定理+约数定理）

阶乘约数

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

定义阶乘 n! = 1 × 2 × 3 × · · · × n!

请问 100! （100 的阶乘）有多少个正约数。

思路：

分析：

根据唯一分解定理：对一个大于1 的整数n，n可以分解质因数为：

其中pi表示n的第i个质因子，ai表示pi的幂次 如18 = 2 ^ 1 * 2 ^ 3（此时p1=2,a1=1,p2 = 3,a2=2）

再根据约数定理一个正整数 n 的正约数的个数:

所以我们只要求得 100! 的每个质因子对应的幂次即可求出答案。

对于2 * 3 * 4 * 5（5！= 120）,其质因子有2,3，5，对应的幂次分别为3,1,1,即2^3 * 3 ^1 * 5 ^ 1。

我们再对2,3，4,5做质因数分解：

不难发现 120120 的每个质因子幂次,为2,3,4,5 对应质因子幂次之和。

同理，100! = 1×2×3×…×100，所以它的每个质因子的幂次就为 1,2,3,…,100 的对应质因子的幂次之和。于是我们只要对1∼100 每个数做质因子分解，再对应相加就可得出 100! 的每个质因子的幂次，再根据约数定理即可求解 注意：答案太大，需要开 long long

最后答案为 39001250856960000

#include

using namespace std;

const int N = 1e2 + 10;

int cnt[N]; // cnt[i] 存的是质因子 i 的幂次

int main() {

for(int i = 1 ; i <= 100 ; i ++) {

int x = i;

// 质因子分解

for(int j = 2 ; j * j <= x ; j ++) {

if(x % j == 0) {

while(x % j == 0) x /= j , cnt[j] ++ ; // j是其中一个质因子

}

}

if(x > 1) cnt[x] ++ ;

}

long long ans = 1;

for(int i = 1 ; i <= 100 ; i ++) {

if(cnt[i] != 0) ans *= (cnt[i] + 1);

}

cout << ans;

return 0;

}