题目链接: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; }
|