題目鏈接戳這里（洛谷P3455）

題目描述：

給出 a, b, d, 求滿足 1 ≤ x ≤ a, 1 ≤ y ≤ b, 且 gcd(x,y)=d 的二元組 (x,y) 的數(shù)量。

思路

首先，我們根據(jù)題意可以得到下面這個(gè)式子：
$$ans=\sum _{x=1}^a\sum _{y=1}^b[\gcd (x,y)=d]$$
除掉d，我們得到：
$$ans=\sum _{x=1}^{a/d}\sum _{y=1}^{b/d}[\gcd (x,y)=1]$$
而 [gcd(x,y)=1] 形如 [x = 1]于是我們繼續(xù)化簡：
$$ans=\sum _{x=1}^{a/d}\sum _{y=1}^{b/d}\sum _{k|gcd(x,y)}\mu (k)$$
交換求和順序：
$$ans=\sum _{k|gcd(x,y)}\mu (k)\sum _{x=1}^{a/d}\sum _{y=1}^{b/d}1$$
我們從k = 1開始枚舉 k：
$$ans=\sum _{k=1}^{min(a,b)/d}\mu (k)??\frac{a}{dk}???\frac{b}{dk}?$$
結(jié)束了。
按照整數(shù)分塊的思想來完成代碼，提前處理 mu[i] (莫比烏斯函數(shù)) 的前綴和。

代碼如下：

//Siberian Squirrel #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; //#define ACM_LOCAL typedef long long ll; #define printd(x) printf("%d\n", x) #define printlld(x) printf("%lld\n", x) #define printlf(x) printf("%.3f\n", x) #define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i) #define per(i, l, r) for(int i = l, i##end = r; i >= i##end; --i) const int inf = 0x3f3f3f3f, MAXN = 5e4 + 10, MOD = 1000000007; const double PI = acos(-1); inline int read() {int res = 0;char c = getchar();while (!isdigit(c)) c = getchar();while (isdigit(c)) res = (res << 1) + (res << 3) + (c ^ 48), c = getchar();return res; } inline int ADD(int a, int b) {return (1ll * a + b) % MOD; } inline int MUL(int a, int b) {return 1ll * a * b % MOD; } inline int SUB(int a, int b) {return (a - b) < 0? (a - b + MOD) % MOD: a - b; } // int a, b, d; int prime[MAXN], mu[MAXN], cnt = 0, qianzhui[MAXN]; bool vis[MAXN]; // inline void pre(int n) {mu[1] = 1;for(int i = 2; i <= n; ++i) {if(!vis[i]) prime[++cnt] = i, mu[i] = -1;for(int j = 1; j <= cnt && i * prime[j] <= n; ++j) {vis[i * prime[j]] = true;if(i % prime[j] == 0) {mu[i * prime[j]] = 0;break;} else mu[i * prime[j]] = -mu[i];}}qianzhui[0] = 0;for(int i = 1; i <= n; ++i) qianzhui[i] = qianzhui[i - 1] + mu[i]; } void solve(ll res = 0) {pre(MAXN - 2);int T = read();while(T--) {res = 0;a = read(), b = read(), d = read();a /= d, b /= d;if(a < b) swap(a, b);for(int i = 1, j; i <= b; i = j + 1) {j = min(a / (a / i), b / (b / i));res += (qianzhui[j] - qianzhui[i - 1]) * 1ll * (a / i) * (b / i);}printlld(res);} } int main() { #ifdef ACM_LOCALsigned test_index_for_debug = 1;char acm_local_for_debug = 0;do {if (acm_local_for_debug == '$') exit(0);if (test_index_for_debug > 20)throw runtime_error("Check the stdin!!!");double start_clock_for_debug = clock();solve();double end_clock_for_debug = clock();cout << "Test " << test_index_for_debug << " successful" << endl;cerr << "Test " << test_index_for_debug++ << " Run Time: "<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;cout << "--------------------------------------------------" << endl;} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug)); #elsesolve(); #endifreturn 0; }

總結(jié)

以上是生活随笔為你收集整理的莫比乌斯反演1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。