0%

洛谷 P3455 [POI2007]ZAP-Queries (莫比乌斯函数)

题目链接:P3455 [POI2007]ZAP-Queries

题意

给定 $a,b,d$,求 $\sum_{x=1}^{a} \sum_{y=1}^{b}[gcd(x, y) = d]$。

思路

莫比乌斯函数的一个性质:

设 $a \le b$,对原式转化:

然后预处理 $\mu$ 的前缀和,用一下整除分块求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e4 + 10;
ll a, b, d;

ll mu[maxn], vis[maxn], sum[maxn];
vector<ll> p;

// 莫比乌斯函数的前缀和
void init() {
sum[1] = mu[1] = 1;
for(int i = 2; i < maxn; ++i) {
if(!vis[i]) {
mu[i] = -1;
p.push_back(i);
}
for(int j = 0; j < p.size() && i * p[j] < maxn; ++j) {
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
mu[i * p[j]] = -mu[i];
}
}
for(int i = 2; i < maxn; ++i) {
sum[i] = sum[i - 1] + mu[i];
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
init();
int T;
cin >> T;
while(T--) {
cin >> a >> b >> d;
if(a > b) {
swap(a, b);
}
a /= d;
b /= d;
ll ans = 0;
// 整除分块
for(int i = 1, j; i <= a; i = j + 1) {
j = min(a / (a / i), b / (b / i));
ans += (sum[j] - sum[i - 1]) * (a / i) * (b / i);
}
cout << ans << endl;
}
return 0;
}

欢迎关注我的其它发布渠道