问题分析

我们需要计算满足以下条件的正整数对 $(x,y)$ 的个数：

• $1 \le x \le a$
• $1 \le y \le b$
• $\gcd(x,y) = d$

关键转化

令 $x = d \cdot x'$, $y = d \cdot y'$，则原条件等价于：

• $1 \le x' \le \lfloor a/d \rfloor$
• $1 \le y' \le \lfloor b/d \rfloor$
• $\gcd(x', y') = 1$

问题转化为：计算在 $[1, \lfloor a/d \rfloor] \times [1, \lfloor b/d \rfloor]$ 范围内，互质对的个数。

莫比乌斯反演

定义

设 $A = \lfloor a/d \rfloor$, $B = \lfloor b/d \rfloor$，我们要求：

$$\sum_{i=1}^A \sum_{j=1}^B [\gcd(i,j) = 1]$$

应用莫比乌斯反演

利用莫比乌斯函数的性质：

$$[\gcd(i,j) = 1] = \sum_{d|\gcd(i,j)} \mu(d)$$

因此：

$$\sum_{i=1}^A \sum_{j=1}^B [\gcd(i,j) = 1] = \sum_{i=1}^A \sum_{j=1}^B \sum_{d|\gcd(i,j)} \mu(d) $$

交换求和顺序：

$$= \sum_{d=1}^{\min(A,B)} \mu(d) \sum_{i=1}^{\lfloor A/d \rfloor} \sum_{j=1}^{\lfloor B/d \rfloor} 1 = \sum_{d=1}^{\min(A,B)} \mu(d) \cdot \left\lfloor \frac{A}{d} \right\rfloor \cdot \left\lfloor \frac{B}{d} \right\rfloor $$

算法优化

数论分块

直接计算 $\sum_{d=1}^n \mu(d) \cdot \lfloor A/d \rfloor \cdot \lfloor B/d \rfloor$ 是 $O(n)$ 的，但我们可以利用数论分块优化到 $O(\sqrt{n})$。

观察 $\lfloor A/d \rfloor$ 和 $\lfloor B/d \rfloor$ 的值在连续的 $d$ 区间内是常数。对于区间 $[l, r]$，有：

• $\lfloor A/l \rfloor = \lfloor A/r \rfloor$
• $\lfloor B/l \rfloor = \lfloor B/r \rfloor$

区间的右端点为：

$$r = \min\left( \left\lfloor \frac{A}{\lfloor A/l \rfloor} \right\rfloor, \left\lfloor \frac{B}{\lfloor B/l \rfloor} \right\rfloor \right) $$

前缀和预处理

预处理莫比乌斯函数的前缀和：

for (int i = 1; i < N; i++) {
    mobius[i] += mobius[i - 1];
}

代码解析

莫比乌斯函数计算

void make_mobius(void) {
    // 线性筛预处理最小质因子
    for (int i = 2; i < N; i++) {
        if (prime[i] == 0) {
            for (int j = i; j < N; j += i) {
                prime[j] = i;
            }
        }
    }
    
    mobius[1] = 1;
    // 递推计算莫比乌斯函数
    for (int i = 2; i < N; i++) {
        if (i % (prime[i]*prime[i]) == 0) {
            mobius[i] = 0;  // 有平方因子
        } else {
            mobius[i] = -mobius[i / prime[i]];  // 积性函数性质
        }
    }
    
    // 计算前缀和
    for (int i = 1; i < N; i++) {
        mobius[i] += mobius[i - 1];
    }
}

查询处理

void test() {
    int a, b;
    cin >> a >> b;
    int d;
    cin >> d;
    
    a /= d;  // A = floor(a/d)
    b /= d;  // B = floor(b/d)
    
    int n = min(a, b);
    int s = 0;
    
    int l = 1;
    int r = 1;
    
    // 数论分块
    while (l <= n) {
        r = min(a / (a / l), b / (b / l));
        
        // 利用前缀和计算区间和
        s += (mobius[r] - mobius[l - 1]) * (a / l) * (b / l);
        
        l = r + 1;
    }
    
    cout << s << "\n";
}

复杂度分析

• 预处理：$O(N)$，其中 $N = 50,000$
• 每次查询：$O(\sqrt{\min(a,b)})$
• 总复杂度：$O(N + n\sqrt{N})$，其中 $n$ 是查询次数

样例验证

样例1：4 5 2

• $a=4, b=5, d=2$
• $A=2, B=2$
• 计算 $\sum_{d=1}^2 \mu(d) \cdot \lfloor 2/d \rfloor \cdot \lfloor 2/d \rfloor$
• $d=1$: $\mu(1) \cdot 2 \cdot 2 = 4$
• $d=2$: $\mu(2) \cdot 1 \cdot 1 = -1$
• 结果：$4 - 1 = 3$ ✓

样例2：6 4 3

• $a=6, b=4, d=3$
• $A=2, B=1$
• 计算 $\sum_{d=1}^1 \mu(d) \cdot \lfloor 2/d \rfloor \cdot \lfloor 1/d \rfloor$
• $d=1$: $\mu(1) \cdot 2 \cdot 1 = 2$
• 结果：$2$ ✓

总结

本题通过莫比乌斯反演将数论问题转化为可高效计算的形式，结合数论分块和前缀和优化，实现了对大量查询的高效处理。这是数论中经典的技巧组合，在解决涉及 $\gcd$ 计数的问题时非常有效。