更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19631424

大意

给出 $a,b,d$，求满足 $1 \leq x \leq a$，$1 \leq y \leq b$，且 $\gcd(x,y)=d$ 的二元组 $(x,y)$ 的数量。

思路

也就是说，我们要统计的答案是 $\sum_{x = 1} ^ a \sum_{y = 1} ^ b [\gcd(x, y) = d]$。

我们考虑莫比乌斯反演。

我们令 $x = d \times x', y = d \times y'$，那么原式可化为 $\sum_{x' = 1} ^ {\lfloor \frac{x}{d} \rfloor} \sum_{y' = 1} ^ {\lfloor \frac{y}{d} \rfloor} [\gcd(x', y') = 1]$，我们再利用恒等式 $[\gcd(x, y) = 1] = \sum_{k | \gcd(x, y)} \mu(k)$ 代入，得到答案为 $\sum_{x' = 1} ^ {\lfloor \frac{x}{d} \rfloor} \sum_{y' = 1} ^ {\lfloor \frac{y}{d} \rfloor} \sum_{k | \gcd(x, y)} \mu(k)$，接下来，我们再改变一下，先枚举 $k$，再看那些情况符合的，答案就变为了 $\sum_{k = 1} ^ {\min(\lfloor \frac{x}{d} \rfloor, \lfloor \frac{y}{d} \rfloor)} \mu(k) \lfloor \frac{x}{d} \rfloor \lfloor \frac{y}{d} \rfloor$。

代码

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

const int MAXN = 50005;
int mu[MAXN], pr[MAXN];
bool vis[MAXN];
int sum[MAXN], tot = 0;

void init(int n){
	mu[1] = 1;
	for(int i = 2;i <= n;i ++){
		if(!vis[i]){
			pr[++ tot] = i;
			mu[i] = -1;
		}
		for(int j = 1;j <= tot && pr[j] * i <= n;j ++){
			vis[pr[j] * i] = 1;
			if(i % pr[j] == 0){
				mu[pr[j] * i] = 0;
				break;
			}
			mu[pr[j] * i] = -mu[i];
		}
	}
	for(int i = 1;i <= n;i ++){
		sum[i] = sum[i - 1] + mu[i];
	}
}

int solve(){
	int a, b, d, ans = 0;
	cin >> a >> b >> d;
	if(a > b) swap(a, b);
	a /= d, b /= d;
	for(int l = 1, r;l <= a;l = r + 1){
		r = min(a / (a / l), b / (b / l));
		ans += (sum[r] - sum[l - 1]) * (a / l) * (b / l);
	}
	return ans;
}

int main(){
	init(50000);
	int t; cin >> t;
	while(t --){
		cout << solve() << '\n';
	}
	return 0;
}