CSU 1661 Query Mutiple：質因數分解 + 離線查詢區間倍數個數

問題描述

數組 a[1..n] (n≤1e5, a_i≤1e6)，q≤1e5 查詢：區間 [L,R] 中有多少個數是質數 P (P≤1e6) 的倍數。

核心思路：質因數倒排索引

1. 線性篩預計算 1e6 內所有質數及最小質因子 lp[x]。
2. 對每個 a[i] 分解質因子（去重），對每個質因子 p，將位置 i 加入 pos[p] 列表。
3. 查詢 (L,R,P)：在 pos[P] 中二分查找 [L,R] 內位置個數。

線性篩與分解

const int MAXV = 1e6;
int lp[MAXV+1], primes[MAXV], pcnt;
void sieve() {
    for (int i=2;i<=MAXV;++i) {
        if (!lp[i]) lp[i]=i, primes[pcnt++]=i;
        for (int j=0;j pos[MAXV+1];

void addNumber(int idx, int x) {
    while (x > 1) {
        int p = lp[x];
        pos[p].push_back(idx);
        while (x % p == 0) x /= p;
    }
}

查詢處理

int query(int L, int R, int P) {
    auto& v = pos[P];
    if (v.empty()) return 0;
    auto itL = lower_bound(v.begin(), v.end(), L);
    auto itR = upper_bound(v.begin(), v.end(), R);
    return itR - itL;
}

複雜度分析

• 篩法 O(MAXV)。
• 分解 n 個數：每個數質因子數 ≤ 7，總 O(n log MAXV)。
• 每查詢 O(log |pos[P]|)，總 O(q log n)。
• 空間：∑ |pos[p]| ≤ n * 7 ≈ 7e5。

關鍵優化

• 質因數分解時**去重**（同一質因子只記錄一次位置）。
• 用 vector 存儲位置，天然有序（按 idx 遞增插入）。
• 快速 IO（scanf/printf 或關閉同步）。