#|第十一届蓝桥杯大赛软件类决赛 C/C++ 大学 B 组试题 C: 阶乘约数（n!质因数分解） Contests|#|因数&质因数|Other

题目大意 【#|第十一届蓝桥杯大赛软件类决赛 C/C++ 大学 B 组试题 C: 阶乘约数（n!质因数分解）】
文章图片

解题思路实际上就是一个数学知识加上因数个数定理的裸题了。看到约数个数，我们不难想到约数个数定理：

设一个数 x x x的唯一分解式为 p 1 a 1 p 2 a 2 . . . p n a n p_1^{a_1}p_2^{a_2}...p_n^{a_n} p1a1??p2a2??...pnan??，那么其因数个数为 ( a 1 + 1 ) ( a 2 + 1 ) . . ( a n + 1 ) (a_1+1)(a_2+1)..(a_n+1) (a1?+1)(a2?+1)..(an?+1)

阶乘数很大，显然没有办法求出阶乘然后质因数分解。考虑 n ! n! n!的所有质因数都不会超过 n n n，如何求出 n ! n! n!所有的质因数的个数。先分析一个简单的问题，求出 n n n以内质数 p p p的倍数的个数，即 ? n p ? \lfloor \frac{n}{p} \rfloor ?pn??，但是 n n n的阶乘是前 n n n个数相乘，而且对于某个质数，我们只知道它的倍数是没有用的，需要知道每个数对应该质数的幂次是多少。而 n n n以内 p p p的倍数设分解为 p k ? q p^k*q pk?q，显然 k = 1 , 2 , 3 , . . . k=1,2,3,... k=1,2,3,...。那么 ? n p ? \lfloor \frac{n}{p} \rfloor ?pn??求出的只是 k = 1 k=1 k=1的数的个数，还有 k = 2 , 3 , . . . k=2,3,... k=2,3,...的 p p p的倍数，这时我们如果再将上述结果除以 p p p，即 ? ? n p ? p ? \lfloor \frac{\lfloor \frac{n}{p} \rfloor}{p} \rfloor ?p?pn????，也就是 ? n p 2 ? \lfloor \frac{n}{p^2} \rfloor ?p2n??，这求出的是 k = 2 k=2 k=2时的倍数个数，以此类推。将所有结果相加，得到的恰好是 n ! n! n!中质数 p p p的个数。此函数代码如下：

ll cal(int n, int x) { ll ans = 0; while (n) { ans += n / x; n /= x; } return ans; }

以下代码更通用

// // Created by Happig on 2020/11/12 // #include using namespace std; typedef long long ll; const int maxn = 1e6 + 10; vector prime; bitset vis; void euler() { vis.reset(); for (int i = 2; i < maxn; i++) { if (!vis[i]) { prime.push_back(i); } for (int j = 0; j < prime.size() && i * prime[j] < maxn; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } }ll cal(int n, int x) { ll ans = 0; while (n) { ans += n / x; n /= x; } return ans; }ll solve(int n) { ll ans = 1; for (auto p : prime) { if (p > n) break; ans *= cal(n, p) + 1; } return ans; }int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n; euler(); cin >> n; cout << solve(n) << endl; return 0; }