題意#
題目會給非常多筆詢問，每次給你一個整數 \(x\)（最大到 \(10^6\)）。
請你快速回答出 \(x\) 總共有幾個正因數。
思路#
如果只有一筆詢問，最直覺的作法是跑一個迴圈跑到 \(\sqrt{x}\)。
只要找到 \(x\) 能夠整除的數字，就把因數個數加 2（特殊情況剛好是平方根時只加 1）。
這樣計算單一數字的時間複雜度是 \(\mathcal{O}(\sqrt{x})\)。
不過這題的詢問筆數 \(t\) 可能高達 \(10^5\)，如果每次都重算一次一定會超時。
既然會面臨大量查詢，最好的策略就是「預處理」。
我們可以借用「篩法」（類似建構質數表的埃拉托斯特尼篩法 Sieve of Eratosthenes）的概念反向操作。
開一個大小為 \(10^6+1\) 的陣列 cnt，一開始全部設為 0。
接著寫兩層迴圈。
外層枚舉每一個數字 \(i\)。
內層則是把 \(i\) 的所有倍數 \(i \times j\) 找出來，並將 cnt[i*j] 加一（因為 \(i\) 是 \(i \times j\) 的因數）。
這個預處理的動作看似會跑很久，但實際上複雜度是 \(\mathcal{O}(N \log N)\)（調和級數的總和）。
等預建表完成後，我們面對每一次的後續詢問，就能做到 \(\mathcal{O}(1)\) 秒殺。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
// 預處理：建構記錄 1 到 10^6 每個數字有多少因數的陣列
vector<int> cnt(1000001);
for (int i = 1; i <= 1000000; i++) {
// i 是因數，找出所有 i 的倍數 (i*j)，幫它們的因數數量加 1
for (int j = 1; i*j <= 1000000; j++) {
cnt[i*j]++;
}
}
int t;
// 讀取多筆詢問
for (cin >> t; t--;) {
int x; cin >> x;
// O(1) 查表並輸出答案
cout << cnt[x] << '\n';
}
}
