HDU 1695 GCD：欧拉函数筛法 + 容斥原理计数互质对

题目大意

给定 a,b,c,d,k，求满足 gcd(x,y)=k 的有序对 数，其中 x∈[1,c], y∈[1,d]，视 与 为同一对。约束：c,d ≤ 10^5。

数学转化

1. 设 x'=x/k, y'=y/k，则 gcd(x',y')=1
2. 范围变为 x'∈[1, c/k], y'∈[1, d/k]
3. 不妨设 c' ≤ d'，分两段计算：
   • y' ≤ c'：每个 y' 贡献 φ(y') 个互质 x'
   • y' > c'：枚举 y'，用容斥原理算 [1,c'] 中与 y' 互质的数

核心算法

1. 线性筛预处理素数与欧拉函数

const int MAXN = 100000 + 50;
int prime[MAXN], euler[MAXN], primeCnt;

void getPrime() {
    primeCnt = 0;
    for (int i = 2; i < MAXN; ++i) {
        if (!prime[i]) prime[primeCnt++] = i;
        for (int j = 0; j < primeCnt && prime[j] <= MAXN/i; ++j) {
            prime[prime[j]*i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

void getEuler() {
    euler[1] = 1;
    for (int i = 2; i < MAXN; ++i) {
        if (!euler[i]) {
            for (int j = i; j < MAXN; j += i) {
                if (!euler[j]) euler[j] = j;
                euler[j] = euler[j] / i * (i - 1);
            }
        }
    }
}

2. 容斥计算与 y 互质的数

int factor[20][2], factCnt;

int getFactor(int x) { // 分解质因数
    factCnt = 0;
    for (int i = 0; prime[i] <= x/prime[i]; ++i) {
        if (x % prime[i] == 0) {
            factor[factCnt][0] = prime[i];
            factor[factCnt][1] = 0;
            while (x % prime[i] == 0) {
                x /= prime[i];
                factor[factCnt][1]++;
            }
            factCnt++;
        }
    }
    if (x != 1) {
        factor[factCnt][0] = x;
        factor[factCnt][1] = 1;
        factCnt++;
    }
    return factCnt;
}

int solve(int n, int m) { // [1,n] 中与 m 互质的数
    getFactor(m);
    int ans = 0;
    for (int mask = 1; mask < (1<

3. 主流程
int main() {
    getPrime(); getEuler();
    int T; scanf("%d", &T);
    for (int kase = 1; kase <= T; ++kase) {
        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", kase); continue; }
        if (b > d) swap(b, d);
        b /= k; d /= k;
        long long ans = 0;
        for (int i = 1; i <= b; ++i) ans += euler[i];
        for (int i = b+1; i <= d; ++i) ans += solve(b, i);
        printf("Case %d: %lld\n", kase, ans);
    }
    return 0;
}

复杂度分析

预处理：O(MAXN) 线性筛
每查询：O(b + (d-b)·2^ω) ，ω 为质因数个数（≤6），实际极快
空间：O(MAXN)


关键技巧总结

等价变换：gcd(x,y)=k ⇔ gcd(x/k,y/k)=1
对称性利用：设 c≤d，分段累加
欧拉函数前缀和：小范围直接累加 φ
容斥原理：大范围枚举 y 计算互质数