alan23273850 的刷題筆記
d419: 00884 - Factorial Factors
Tags: prefix-sum, prime-table
出處：https://zerojudge.tw/ShowProblem?problemid=d419
提交：https://zerojudge.tw/Submissions?problemid=d419&account=allllllan123456
問題：這題要請你求出多個介於 2 到 1000000 的整數 $n$ 之階乘 $n!$ 可以表達成幾個質數的乘積。
解法：這題的要求和 d131 一樣，差別在於問題的尺度，d131 只要查詢到 100 階乘，但是本題會到 1000000，再加上重複查詢的模式，如果每次都要重新計算的話速度就會很慢，於是最好的作法便是先把答案都存起來，查詢的時候再直接拿來用即可，而這部分還可以利用 prefix sum 的技巧來加速。這題具體的作法就如同程式碼所顯露的，簡單而巧妙，它僅是先統計每個整數它們各自包含所有形如 $p^i$ 之因數的個數，例如 $24=2^3\cdot3^1$ 包含四個 $p^i$ 因數 $2^1$、$2^2$、$2^3$、$3^1$，那麼 24 便可以表達成 4 個質數相乘，再從前面加總過來，就能知道該數的階乘可以表達成幾個質數相乘。
1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAX = 1000000;
5int num[MAX+1]; // for auto initialization
6
7int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
8 int n;
9 for (int p=2; p<MAX; p++)
10 if (!num[p]) // only traverse if it is a prime
11 for (long long pi=p; pi<=MAX; pi*=p)
12 for (int pik=pi; pik<=MAX; pik+=pi)
13 num[pik]++;
14 for (int i=3; i<=MAX; i++)
15 num[i] += num[i-1];
16 while (cin >> n)
17 cout << num[n] << '\n';
18 return 0;
19}