RGCDQ 題解：線段樹 + 數論求區間最大 GCD

題目大意

查詢區間 [n, m] 內所有整數的素因子個數的最大公約數（GCD）。

核心觀察

1. 10⁶ 以內整數素因子個數 ≤ 7（2×3×5×7×11×13×17 = 510510，再乘 19 超過 10⁶）
2. 因此每個數的「素因子個數」只能是 1~7
3. 區間內各數的素因子個數統計出現次數 cnt[1..7]
4. 答案 = max{ k | cnt[k] > 0 且存在 i,j 使得 gcd(i,j) = k }
   實際上：對所有出現的素因子個數 i,j 計算 gcd(i,j) 取最大值

線段樹結構設計

• 葉節點：對應單個整數，存 freq[8]（下標 1~7 為素因子個數出現次數，0 或 1）
• 內部節點：freq[k] = left.freq[k] + right.freq[k]
• 查詢區間 [L, R] 彙總 sum[8]
• 節點用 short 存儲（計數 ≤ 區間長度 ≤ 10⁵，short 足夠），節省記憶體

關鍵步驟

1. 線性篩預處理素因子個數

const int MAXN = 1e6;
int prime[MAXN], phi[MAXN], cnt_pf[MAXN]; // cnt_pf[i] = i的素因子個數
bool vis[MAXN];
void linear_sieve() {
    for (int i = 2; i < MAXN; ++i) {
        if (!vis[i]) { prime[++prime[0]] = i; cnt_pf[i] = 1; }
        for (int j = 1; j <= prime[0] && i * prime[j] < MAXN; ++j) {
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                cnt_pf[i * prime[j]] = cnt_pf[i] + 1;
                break;
            } else {
                cnt_pf[i * prime[j]] = cnt_pf[i] + 1;
            }
        }
    }
}

2. 線段樹建樹與查詢

short tree[MAXN*4][8]; // [節點][素因子個數] = 計數
void build(int node, int l, int r) {
    if (l == r) {
        tree[node][cnt_pf[l]] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(node<<1, l, mid);
    build(node<<1|1, mid+1, r);
    for (int k = 1; k <= 7; ++k)
        tree[node][k] = tree[node<<1][k] + tree[node<<1|1][k];
}
void query(int node, int l, int r, int ql, int qr, short *res) {
    if (ql <= l && r <= qr) {
        for (int k = 1; k <= 7; ++k) res[k] += tree[node][k];
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid) query(node<<1, l, mid, ql, qr, res);
    if (qr > mid) query(node<<1|1, mid+1, r, ql, qr, res);
}

3. 計算答案

short sum[8] = {0};
query(1, 1, MAXN, n, m, sum);
int ans = 0;
for (int i = 1; i <= 7; ++i)
    if (sum[i])
        for (int j = i; j <= 7; ++j)
            if (sum[j])
                ans = max(ans, gcd(i, j));

複雜度

• 預處理：O(MAXN) 線性篩
• 建樹：O(MAXN)
• 單次查詢：O(log MAXN × 7) ≈ O(log MAXN)
• 空間：4×MAXN×8×2 bytes ≈ 64 MB，符合限制

優化點

1. 用 short 而非 int 存計數，內存減半
2. 線性篩同時得到素因子個數，無需額外分解
3. 查詢彙總直接累加到靜態數組，避免遞歸返回值拷貝

總結

本題巧妙利用「素因子個數 ≤ 7」這一數論性質，將問題轉化為區間頻次統計 + 小範圍枚舉 GCD。線段樹維護 7 維頻次向量，查詢後 O(7²) 枚舉即可得答案，體現了數論與數據結構結合的典型思路。