P3455 [POI 2007] ZAP-Queries是什么查询？
摘要：P3455 [POI 2007] ZAP-Queries 大意 给出 (a,b,d)，求满足 (1 leq x leq a)，(1 leq y leq b)，且 (gcd(x,y)=d) 的二元组 ((x,y)
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;
}