HDU 4407：區間互質數求和與單點修改——容斥原理應用

編輯：關於C語言

HDU 4407：區間互質數求和與單點修改——容斥原理應用

題意

有一個初始為 1~n 的數列 {A_n}，支援兩種操作（最多 1000 次）：
1. 查詢區間 [a, b] 中與 p 互質的數的和。
2. 將數列中某位置的值修改。

分析

初始數列為 1,2,...,n，後續有修改。先用容斥原理求解 1~x 中與 p 互質的數的和，再處理修改帶來的差值。
容斥原理步驟：
1. 對 p 質因子分解，得不同質因子集合。
2. 1~x 中與 p 不互質的數，即能被至少一個質因子整除的數。利用容斥原理計算這些數的和。
3. 1~x 中與 p 互質的數的和 = 1+2+...+x - 不互質數的和。
4. 查詢 [a,b] 答案 = solve(b) - solve(a-1)。
5. 修改操作：維護一個 map 記錄被修改位置的新值。查詢時，遍歷 map 中落在 [a,b] 的修改，若原值與 p 互質則減去原值，若新值與 p 互質則加上新值。
注意：數據可能超 int，需用 long long。修改操作不超過 1000 次，map 遍歷可接受。

容斥原理計算互質數和

設 p 的不同質因子為 f₁..f_k。
不互質數和 = Σ(倍數和) - Σ(兩兩最小公倍數倍數和) + Σ(三三...)...
即對質因子子集遞歸/DFS，奇數個質因子相加，偶數個相減。
某子集乘積為 M，1~x 中 M 的倍數和 = M × (1+2+...+⌊x/M⌋) = M × t(t+1)/2，t = x/M。

參考代碼框架 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXV = 400005;
int primes[MAXV], primeCnt;
bool isComp[MAXV];
vector factors[MAXV]; // 預處理每個數的質因子

void sieve() {
    for (int i = 2; i < MAXV; i++) {
        if (!isComp[i]) primes[primeCnt++] = i;
        for (int j = 0; j < primeCnt && i * primes[j] < MAXV; j++) {
            isComp[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
    for (int i = 2; i < MAXV; i++) {
        int x = i;
        for (int p : primes) {
            if (p * p > x) break;
            if (x % p == 0) {
                factors[i].push_back(p);
                while (x % p == 0) x /= p;
            }
        }
        if (x > 1) factors[i].push_back(x);
    }
}

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

// 計算 1..n 中與 p 互質的數的和
ll solve(ll n, int p) {
    if (n <= 0) return 0;
    const vector &fac = factors[p];
    int k = fac.size();
    ll total = n * (n + 1) / 2;
    ll notCoprime = 0;
    // 遍歷非空子集
    for (int mask = 1; mask < (1 << k); mask++) {
        ll prod = 1, bits = 0;
        for (int i = 0; i < k; i++) if (mask & (1 << i)) {
            prod *= fac[i];
            bits++;
        }
        ll t = n / prod;
        ll sumMul = prod * t * (t + 1) / 2;
        if (bits & 1) notCoprime += sumMul;
        else notCoprime -= sumMul;
    }
    return total - notCoprime;
}

int main() {
    sieve();
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        unordered_map modified;
        while (m--) {
            int op; scanf("%d", &op);
            if (op == 2) {
                int x, c; scanf("%d%d", &x, &c);
                modified[x] = c;
            } else {
                int x, y, p; scanf("%d%d%d", &x, &y, &p);
                ll ans = solve(y, p) - solve(x - 1, p);
                for (auto &kv : modified) {
                    int pos = kv.first, val = kv.second;
                    if (pos < x || pos > y) continue;
                    if (gcd(pos, p) == 1) ans -= pos;
                    if (gcd(val, p) == 1) ans += val;
                }
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}