HDU 1695 GCD：容斥原理 + 歐拉函數計數互質數對

問題描述

給定 a,b,c,d,k (a=c=1, b,d ≤ 100,000, k ≤ 100,000)，求滿足 gcd(x,y)=k 的數對 (x,y) 個數，其中 1≤x≤b, 1≤y≤d。無序數對：(x,y) 和 (y,x) 視為同一對。

數學轉化

1. 令 x'=x/k, y'=y/k，則 gcd(x',y')=1
2. 範圍變為 1≤x'≤b/k, 1≤y'≤d/k
3. 設 B=b/k, D=d/k，假設 B≤D

分段計數策略

將 y' 分為兩段：[1, B] 和 [B+1, D]

第一段：1 ≤ x',y' ≤ B

有序數對 (x',y')，x'

第二段：1 ≤ x' ≤ B, B+1 ≤ y' ≤ D

對固定 y'，求 1~B 中與 y' 互質的數個數。用容斥原理：

• 分解 y' 的質因子：p₁, p₂, ..., pₘ
• 能被至少一個質因子整除的數 = Σ C(m,1) - Σ C(m,2) + Σ C(m,3) - ...
• 互質數 = B - 上述結果

完整代碼

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 100000;
int phi[MAXN + 1];
int primes[MAXN], pcnt;
bool isComp[MAXN + 1];

void linearSieve() {
    phi[1] = 1;
    for (int i = 2; i <= MAXN; ++i) {
        if (!isComp[i]) { primes[pcnt++] = i; phi[i] = i - 1; }
        for (int j = 0; j < pcnt && i * primes[j] <= MAXN; ++j) {
            int p = primes[j], ip = i * p;
            isComp[ip] = true;
            if (i % p == 0) { phi[ip] = phi[i] * p; break; }
            else phi[ip] = phi[i] * (p - 1);
        }
    }
}

int getFactors(int x, int* fac) {
    int cnt = 0;
    for (int i = 0; i < pcnt && primes[i] * primes[i] <= x; ++i) {
        if (x % primes[i] == 0) {
            fac[cnt++] = primes[i];
            while (x % primes[i] == 0) x /= primes[i];
        }
    }
    if (x > 1) fac[cnt++] = x;
    return cnt;
}

int countCoprime(int B, int y) {
    int fac[10], cnt = getFactors(y, fac);
    int res = 0;
    for (int mask = 1; mask < (1 << cnt); ++mask) {
        int lcm = 1, bits = 0;
        for (int i = 0; i < cnt; ++i)
            if (mask & (1 << i)) { lcm *= fac[i]; ++bits; }
        if (bits & 1) res += B / lcm;
        else res -= B / lcm;
    }
    return B - res;
}

int main() {
    linearSieve();
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        int a, b, c, d, k;
        scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
        if (k == 0 || k > b || k > d) { printf("Case %d: 0\n", cas); continue; }
        b /= k; d /= k;
        if (b > d) swap(b, d);
        
        long long ans = 0;
        for (int i = 2; i <= b; ++i) ans += phi[i];
        for (int i = b + 1; i <= d; ++i) ans += countCoprime(b, i);
        
        printf("Case %d: %lld\n", cas, ans);
    }
    return 0;
}

關鍵優化

1. 線性篩預計算 φ：O(MAXN) 一次性完成
2. 質因子分解快速化：預存質數表，分解 O(√y / log y)
3. 容斥位掩碼枚舉：質因子數 ≤ 6 (2×3×5×7×11×13=30030>100000)，最多 2⁶=64 子集

複雜度

• 預處理：O(MAXN)
• 每測試用例：O(B + (D-B)·2^ω) ≈ O(10⁵) 以內
• 3000 測試用例總時間 < 1s