HDU 4407 Sum：容斥原理 + 離線修改處理

題目大意

維護一個初始為 1..n 的數列 A，支持兩種操作（共 M ≤ 1000 次）：

1. 查詢區間 [a, b] 中與給定整數 p 互質的元素之和。
2. 單點修改：將位置 p 的值改為 v。

核心思路：容斥原理轉化

求與 p 互質的數之和，等價於區間總和 減去 與 p 不互質（即與 p 有公約數）的數之和。後者可用容斥原理計算：設 p 的質因子為 prime[1..k]，則與 p 不互質的數即為能被至少一個質因子整除的數。容斥公式為：

Sum = Σ (-1)^(cnt+1) * (倍數之和)，其中遍歷所有非空質因子子集，cnt 為子集大小，倍數之和為等差數列求和。

靜態查詢函數 solve(n, p)

LL solve(int n, int p) { // 求 [1, n] 中與 p 不互質的數之和
    LL ans = 0;
    int sz = prime[p].size();
    int subsets = (1 << sz);
    for (int mask = 1; mask < subsets; mask++) {
        LL lcm = 1, cnt = 0;
        for (int i = 0; i < sz; i++) if (mask >> i & 1) {
            lcm *= prime[p][i];
            cnt++;
            if (lcm > n) break;
        }
        if (lcm > n) continue;
        LL num = n / lcm;
        LL sum = (lcm + lcm * num) * num / 2; // 等差數列和
        if (cnt & 1) ans += sum; else ans -= sum;
    }
    return ans;
}

處理修改操作：離線 + Map 記錄

修改次數較少（≤ M），可將所有修改記錄在 map ms 中（key=位置, value=新值）。查詢時：

1. 先用靜態 solve 算出原始數列在 [l, r] 中與 p 不互質的和 ans。
2. 遍歷 ms 中所有修改記錄，若位置落在 [l, r] 內，則調整 ans：
   • 若舊值（即位置索引本身，因初始 A[i]=i）與 p 不互質，減去舊值。
   • 若新值與 p 不互質，加上新值。
   • 同時修正區間總和：ans += old_val - new_val（因總和變了）。
3. 最終答案 = (su[r] - su[l-1]) - ans，其中 su[i] 為 1..i 的前綴和。

複雜度分析

• 預處理質因子篩：O(MAX log log MAX)，MAX=400000。
• 單次查詢容斥：O(2^k)，k 為質因子個數（p≤400000 時 k≤6），極快。
• 遍歷修改記錄：O(修改次數) ≤ O(M)。
• 總體：O(M * (2^k + M))，M≤1000 完全可行。

代碼關鍵點

• 使用 vector prime[maxn] 存儲每個數的質因子。
• map 自動按位置排序，遍歷方便。
• 注意 long long 防溢出。

總結

本題巧妙結合了數論（容斥原理）與離線處理修改的技巧。利用修改操作較少的特性，將動態問題轉化為靜態查詢加少量修正，避免了複雜的數據結構，代碼簡潔高效。