P3455 [POI 2007] ZAP-Queries
大意
给出 \(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;
}