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;
}