Bayan 2015 Contest Warm Up D 題：區間 GCD 查詢解法分析

問題描述

給定一個長度為 n 的整數序列 a₁, a₂, …, a_n，以及 q 個查詢 x₁, x₂, …, x_q。對於每個查詢 x_i，需要計算有多少個區間 (l, r)（1 ≤ l ≤ r ≤ n）使得該區間內所有數的最大公約數（GCD）恰好等於 x_i。

核心思路

這是一道經典的區間 GCD 統計問題。關鍵觀察是：對於固定的右端點 r，當左端點 l 從 r 向左移動時，區間 [l, r] 的 GCD 值只會發生 O(log maxA) 次變化（因為每次變化至少減半）。因此，我們可以維护以每個位置結尾的所有可能 GCD 值及其出現次數。

演算法流程

1. 預處理所有區間的 GCD 計數：使用一個 map（或 unordered_map）ans 記錄每個 GCD 值在所有區間中出現的總次數。
2. 動態維護以當前位置結尾的區間 GCD：
   • 設 mp 存儲以 i 結尾的所有區間的 GCD 值及其個數。
   • 從左向右遍歷數組，對於位置 i+1，新的 mp2 由 mp 中的每個 (g, cnt) 經過 gcd(g, a_i+1) 轉移而來，同時加上單元素區間 a_i+1。
   • 將 mp2 中的計數累加到全局 ans 中，然後令 mp = mp2 繼續下一輪。
3. 回答查詢：直接在 ans 中查找 x_i 對應的值，若不存在則為 0。

複雜度分析

每個位置的 mp 大小不超過 O(log maxA)，轉移操作總次數為 O(n log maxA)。使用哈希表實現時，平均時間複雜度約為 O(n × 因子個數)，完全滿足 2 秒時限。

關鍵代碼片段

map<long long, long long> ans, mp, mp2;
for (int i = 0; i < n; ++i) {
    mp2.clear();
    mp2[a[i]]++;
    for (auto &p : mp) {
        long long g = gcd(p.first, a[i]);
        mp2[g] += p.second;
    }
    for (auto &p : mp2) ans[p.first] += p.second;
    mp.swap(mp2);
}

這種「以右端點為狀態、利用 GCD 變化次數少」的技巧，廣泛應用於區間 GCD、LCM 等相關問題中。