P3455 [POI2007]ZAP-Queries (莫比乌斯反演

https://www.luogu.org/problem/P3455

题意：求满足x<=a,y<=b，gcd(x,y)=d的x,y对数。

分析：莫比乌斯反演和除法分块。

egin{split}
sum_{i=1}^{a}sum_{j=1}^{b}[gcd(i,j)=d] ewline
sum_{i=1}^{a/d}sum_{j=1}^{b/d}[gcd(i,j)=1] ewline
sum_{i=1}^{a/d}sum_{j=1}^{b/d}sum_{k|gcd(i,j)}^{ }mu(k) ewline
sum_{k=1}^{min(a/d,b/d)}mu(k)sum_{i=1}^{a/d}[k|i]sum_{j=1}^{b/d}[k|j] ewline
a'=a/d , b'=b/d ewline
sum_{k=1}^{min(a',b')}mu(k)[frac{a'}{k}][frac{b'}{k}]
end{split}

此时为n，可以再分块成$sqrt{n}$。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;
int mu[maxn],prime[maxn],cnt=0;
bool vis[maxn];

inline void init(){
    mu[1] = 1;
    for(int i=2;i<maxn;i++){
        if (vis[i] ==false){
            prime[cnt++] = i;
            mu[i] = -1;
        }
        for(int j=0;j<cnt&&prime[j]*i<maxn;j++){
            vis[i*prime[j]] = true;
            if(i%prime[j]==0) {mu[i*prime[j]] = 0;break;}
            else mu[i*prime[j]] = -mu[i];
        }
    }
    for(int i=2;i<maxn;i++)
        mu[i] += mu[i-1];
}

inline int solve(int a,int b){
    int ans = 0;
    if(a>b) swap(a,b);
    for(int l=1,r;l<=a;l=r+1){
        r = min(a/(a/l),b/(b/l));
        ans += (mu[r]-mu[l-1])*(a/l)*(b/l);
    }
    return ans;
}

int main(){
    init();
    int t,a,b,d;
    cin>>t;
    while(t--){
        cin>>a>>b>>d;
        cout<<solve(a/d,b/d)<<endl;
    }
    return 0;
}