lanqiaoOJ 1020：阶乘约数 ← 整数唯一分解定理 + 约数个数定理

​【题目来源】
https://www.lanqiao.cn/problems/1020/learning/

【题目描述】
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
定义阶乘 n!=1×2×3×……×n。
请问 100!（100的阶乘）有多少个正约数。

【算法分析】
● 约数个数定理：设正整数 n 的质因数分解为 n=p₁ᵏ¹×p₂ᵏ²×...×pₘᵏᵐ，其中 p1，p2，…，pm 是互不相同的质数， ki 是质因子 pi 在 n 中的指数。那么，n 的正约数个数为 (k₁+1)(k₂+1)…(kₘ+1)。

● 推论：设 n! 的质因数分解为 n!=p₁ᵏ¹×p₂ᵏ²×...×pₘᵏᵐ，其中 ki 是质因子 pi 在 n! 中的指数。那么，由约数个数定理知 (n!)^2=(p₁ᵏ¹×p₂ᵏ²×...×pₘᵏᵐ)^2 的正约数个数为 (2k₁+1)(2k₂+1)…(2kₘ+1)。
→ 此推论成立的原理：方程 a×b=M 的正整数解 (a,b) 的组数，等于 M 的正约数个数。因为，每一个约数 d 都唯一对应一组解 (d, M/d)。​​​​​​​

【算法代码】

#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=105;
int a[N];void cal(int n) {for(int i=2; i*i<=n; i++) {if(n%i) continue;while(n%i==0) n/=i,a[i]++;}if(n>1) a[n]++;
}int main() {int n=100;for(int i=2; i<=n; i++) cal(i);LL ans=1;for(int i=1; i<=n; i++) {if(a[i]>0) ans=ans*(a[i]+1);}cout<<ans<<endl;return 0;
}/*
39001250856960000
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/158097108
https://blog.csdn.net/hnjzsyjyj/article/details/158074254


 

​