题面
【问题描述】
定义阶乘 n! = 1 × 2 × 3 × · · · × n。
请问 100! （100 的阶乘）有多少个约数。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
思路
数论。根据 质因数分解定理，对于任意一个大于0的整数 n， 都可以分解为如下形式：
其中， 为质数。则该整数 n 的约数个数s为：
则可以知道，本题的解决方案为，枚举出 1 - 100 之间的没个数， 对每个数进行分解质因数，再将所有的分解出的质数加入该质数计数器，最后将 出现的质数的次数+1 ，再累乘则得出结果。
答案：39001250856960000
代码
#include<iostream>
using namespace std;
int cnt[105];
void divide(int x) {
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
while (x % i == 0) {
cnt[i]++;
x /= i;
}
}
}
if (x > 1) cnt[x]++;
}
int main() {
long long res = 1;
for (int i = 1; i <= 100; i++) divide(i);
for (int i = 1; i <= 100; i++) res *= cnt[i] + 1;
cout << res << endl;
return 0;
}
| 标题： | 2020第十一届蓝桥杯国赛-C阶乘约数 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/106 |
| 更新： | 2022-09-18 22:39:19 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |