URL: (Luogu)https://www.luogu.org/problem/show?pid=3455
(BZOJ)http://www.lydsy.com/JudgeOnline/problem.php?id=1101

題目大意:
有t次詢問(wèn)(t≤5e4), 每次給定a,b,d, 詢問(wèn)有多少對(duì)(x,y)滿足x<=a, y<=b, gcd(a,b)=d. 0<=d<=a,b<=5e4

思路分析:
首先，需要注意的是，要特殊處理d=0的情況，答案為0.
對(duì)于d≥1, 采用莫比烏斯反演解決:
先將a/=d, b/=d, 因此只需求gcd(x,y)=1的數(shù)的對(duì)數(shù)。
令F[i]表示1≤x≤a,1≤y≤b且i|gcd(x,y)的a,b總數(shù), f[i]表示gcd(x,y)=i的數(shù)的對(duì)數(shù)(此處a,b都已經(jīng)除以d).因此問(wèn)題轉(zhuǎn)化為求f(1).
根據(jù)莫比烏斯反演公式:

F(n)=∑n|xf(x),f(n)=∑n|xF(x)μ(xn)
因此， f(1)=∑1|xF(x)μ(x)
而顯然我們有 F(x)=[ax][bx], 因此可以 O(1)地求出F(x), 也就可以 O(min(a,b))地求出f(1)了。(莫比烏斯反演函數(shù) μ(x)可在線性篩中求出)
可是這樣還不夠。算算復(fù)雜度，發(fā)現(xiàn)會(huì)TLE.
注意到一個(gè)性質(zhì): 對(duì)于 x≤a√, [ax]的值變化得很快, [ax]的變化速度遠(yuǎn)高于 x的變化速度。而對(duì)于x>a√, [ax]的值變化得很慢, 遠(yuǎn)低于 x的變化速度。因此，我們可以求出所有使得[ax]的值變化的點(diǎn)x， 共有 O(n√)個(gè)(實(shí)際上帶一個(gè)常數(shù)2), 然后我們對(duì)b做同樣的操作。將所有影響 [ax]和 [bx]的值的點(diǎn)都從小到大排序記錄下來(lái)，處理莫比烏斯函數(shù)的前綴和, 每一個(gè)點(diǎn)代表一個(gè)區(qū)間，這個(gè)區(qū)間內(nèi)所有的數(shù) [ax]與 [bx]的值分別與這個(gè)數(shù) [ax]和 [bx]相等。然后這一段區(qū)間對(duì)答案的貢獻(xiàn)就是區(qū)間的 μ()之和乘以 [ax][bx].

代碼實(shí)現(xiàn)

#include<cstdio> #include<algorithm> #include<cmath> using namespace std;const int N = 5e4; const int NN = 317; int p[N+2]; bool f[N+2]; int mu[N+2]; int s[N+2]; int g[(NN<<2)+2]; int h[(NN<<2)+2]; int a,b,d,m;void Mobius() {f[1] = true; mu[1] = 1; m = 0;for(int i=2; i<=N; i++){if(!f[i]) {p[++m] = i; mu[i] = -1;}for(int j=1; p[j]*i<=N; j++){f[p[j]*i] = true;if(i%p[j]==0){mu[i*p[j]] = 0;break;}else mu[i*p[j]] = -mu[i];}} }void merge(int aa,int bb) {int i = 1,j = (aa<<1)+1,k = 1;while(i<=(aa<<1) && j<=(aa<<1)+(bb<<1)){if(h[i]<h[j]) g[k++] = h[i++];else g[k++] = h[j++];}while(i<=(aa<<1)) g[k++] = h[i++];while(j<=(aa<<1)+(bb<<1)) g[k++] = h[j++]; }int main() {int t; scanf("%d",&t);Mobius(); s[0] = 0;for(int i=1; i<=N; i++) s[i] = s[i-1]+mu[i];while(t--){scanf("%d%d%d",&a,&b,&d);if(d==0) {printf("0\n"); continue;}if(a>b) swap(a,b);a /= d; b /= d;int aa = (int)sqrt(a),bb = (int)sqrt(b);long long ans = 0ll;for(int i=1; i<=aa; i++) h[i] = i;for(int i=aa; i>=1; i--) h[(aa<<1)-i+1] = a/i;//保證h[]在1~(aa<<1)范圍內(nèi)有序for(int i=1; i<=bb; i++) h[i+(aa<<1)] = i;for(int i=bb; i>=1; i--) h[(aa<<1)+(bb<<1)-i+1] = b/i;//保證h[]在1~(bb<<1)范圍內(nèi)有序merge(aa,bb);//將[1,aa<<1]與[aa<<1+1,aa<<1+bb<<1]歸并起來(lái)for(int i=1; i<=(aa<<1)+(bb<<1); i++){ans += (long long)(s[g[i]]-s[g[i-1]])*(a/g[i])*(b/g[i]);}printf("%lld\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1101 Luogu P3455 POI 2007 Zap (莫比乌斯反演+分块)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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