年更选手报道！
luogu P3455 [POI2007] ZAP-Queries
莫比乌斯反演。
令：\(a\le b\)
求：
\[\sum\limits_{i=1}^a\sum\limits_{j=1}^b[\gcd(i,j)=x]
\]
消掉 \(x\)：
\[=\sum\limits_{i=1}^{\left\lfloor\frac{a}{x}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{b}{x}\right\rfloor}[\gcd(i,j)=1]
\]
根据莫比乌斯的定义：
\[=\sum\limits_{i=1}^{\left\lfloor\frac{a}{x}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{b}{x}\right\rfloor}\sum_{d|\gcd(i,j)} \mu(d)
\]
改成和的形式：
\[=\sum\limits_{i=1}^{\left\lfloor\frac{a}{x}\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{b}{x}\right\rfloor}\sum_{d=1}^{\left\lfloor\frac{a}{x}\right\rfloor} \mu(d) \times [d | \gcd(i,j)]
\]
移项：
\[=\sum\limits_{d=1}^{\left\lfloor\frac{a}{x}\right\rfloor} \mu(d)\sum\limits_{i=1}^{\left\lfloor\frac{b}{x}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{a}{x}\right\rfloor} \times [d | \gcd(i,j)]
\]
显然 \(d|i,d|j\)，又因为满足条件的 \(i\) 在 \(1 \sim \left\lfloor\frac{a}{x}\right\rfloor\) 中出现 \(\left\lfloor\frac{a}{x \times d}\right\rfloor\) 次，\(j\) 在 \(1 \sim \left\lfloor\frac{b}{x}\right\rfloor\) 中出现 \(\left\lfloor\frac{b}{x \times d}\right\rfloor\) 次，所以：
\[=\sum\limits_{d=1}^{\left\lfloor\frac{a}{x}\right\rfloor} \mu(d)\left\lfloor\frac{a}{x \times d}\right\rfloor\left\lfloor\frac{b}{x \times d}\right\rfloor
\]
然后可以预处理出 \(\mu\) 的前缀和，另外的整除分块即可。时间复杂度 \(\mathcal{O(m \log \sqrt{n})}\)。
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4;
int pri[N + 100], cnt, mu[N + 100], a, b, x, n, sumu[N + 100];
bool vis[N + 100];
void solve() {
cin >> a >> b >> x;
if (a > b) {
swap(a, b);
}
a /= x;
b /= x;
int ans = 0;
for (int l = 1, r; l <= a; l = r + 1) {
r = min(a / (a / l), b / (b / l));
ans += (a / l) * (b / l) * (sumu[r] - sumu[l - 1]);
}
cout << ans << endl;
}
void init() {
mu[1] = 1;
vis[1] = 1;
for (int i = 2; i <= N; i++) {
if (!vis[i]) {
pri[++cnt] = i;
mu[i] = -1;
}
for (int j = 1; j <= cnt && i * pri[j] <= N; j++) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) {
mu[i * pri[j]] = 0;
break;
} else {
mu[i * pri[j]] = mu[i] * mu[pri[j]];
}
}
}
for (int i = 1; i <= N; i++) {
sumu[i] = sumu[i - 1] + mu[i];
}
}
signed main() {
init();
cin >> n;
while (n--) {
solve();
}
return 0;
}