P2522 [HAOI2011] Problem b的：HAOI2011 Problem b问题如何解决？
摘要：P2522 [HAOI2011] Problem b 大意 [sum_{x=a}^b sum_{y=c}^d [gcd(x, y) = k] ]思路 利用 容斥原理，我们可以将区间 ([a, b]) 和 ([c, d])
P2522 [HAOI2011] Problem b
大意
\[\sum_{x=a}^b \sum_{y=c}^d [\gcd(x, y) = k]
\]
思路
利用 容斥原理，我们可以将区间 \([a, b]\) 和 \([c, d]\) 的限制简化为从 \(1\) 开始的形式。令 \(f(n, m, k)\) 表示 \(1 \le x \le n, 1 \le y \le m\) 且 \(\gcd(x, y) = k\) 的个数，则原式等于：
\[f(b, d, k) - f(a-1, d, k) - f(b, c-1, k) + f(a-1, c-1, k)
\]
对于 \(f(n, m, k)\)，满足 \(\gcd(x, y) = k\) 等价于 \(\gcd(\frac{x}{k}, \frac{y}{k}) = 1\)。
令 \(n' = \lfloor \frac{n}{k} \rfloor, m' = \lfloor \frac{m}{k} \rfloor\)，我们要算的是：
\[\sum_{i=1}^{n'} \sum_{j=1}^{m'} [\gcd(i, j) = 1]
\]
利用莫比乌斯函数的性质 \(\sum_{d|\gcd(i,j)} \mu(d) = [\gcd(i, j) = 1]\)，代入得：
\[\sum_{i=1}^{n'} \sum_{j=1}^{m'} \sum_{d|\gcd(i, j)} \mu(d)
\]
通过枚举 \(d\) 调整求和顺序：
\[\sum_{d=1}^{\min(n', m')} \mu(d) \lfloor \frac{n'}{d} \rfloor \lfloor \frac{m'}{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];
}
}
long long count(int a, int b, int d){
a /= d, b /= d;
if(a > b) swap(a, b);
long long ans = 0;
for(int l = 1, r;l <= a;l = r + 1){
r = min(a / (a / l), b / (b / l));
ans += (long long)(sum[r] - sum[l - 1]) * (a / l) * (b / l);
}
return ans;
}
int main(){
init(50000);
int t; cin >> t;
while(t --){
int a, b, c, d, k;
cin >> a >> b >> c >> d >> k;
long long res = count(b, d, k) - count(a - 1, d, k) - count(b, c - 1, k) + count(a - 1, c - 1, k);
cout << res << '\n';
}
return 0;
}