P2522 [HAOI2011]Problem b

求： ${\sum_{x=a}^{b}\sum_{y=c}^{d}[gcd(x,y)=k]}$
根据容斥原理，可以分为四部分来求，每一部分都可以拆成：

${\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)=k]}$

考虑到 ${gcd(x,y)=1}$ 可以转化，所以为了化简式子，可以：原式

$={\sum_{x=1}^{⌊\frac{n}{k}⌋}\sum_{y=1}^{⌊\frac{m}{k}⌋}[gcd(x,y)=1]}$

$={\sum_{x=1}^{⌊\frac{n}{k}⌋}\sum_{y=1}^{⌊\frac{m}{k}⌋}\varepsilon(gcd(x,y))}$

$={\sum_{x=1}^{⌊\frac{n}{k}⌋}\sum_{y=1}^{⌊\frac{m}{k}⌋}\sum_{d|gcd(x,y)}\mu(d)}$

式子出现莫比乌斯函数后，通常可以考虑交换求和顺序，枚举 ${d|gcd(x,y)}$ ,即：

${\sum_{d=1}\mu(d)\sum_{x=1}^{⌊\frac{n}{k}⌋}[d|x]\sum_{y=1}^{⌊\frac{m}{k}⌋}[d|y]}$

${\sum_{d=1}\mu(d)⌊\frac{n}{kd}⌋⌊\frac{m}{kd}⌋}$

很显然，只要预处理莫比乌斯函数，然后用数论分块求解式子。

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+7;
int mu[maxn + 1],sum[maxn+1];
int work(int n,int m) {
    int tot=min(n,m);
    int x,y,r,ans=(0);
    for(int i=1;i<=tot;++i) {
        x=n/i,y=m/i;
        r=min(n/x,m/y);
        ans+=(sum[r]-sum[i-1])*x*y;
        i=r;
    }
    return ans;
}
signed main() {
    cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
    mu[1] = 1;
    for (int i = 1; i <= maxn; i++) {
        for (int j = 2 * i; j <= maxn; j += i) {
            mu[j] -= mu[i];
        }
        sum[i]=sum[i-1]+mu[i];
    }
    int T,a,b,c,d,k;
    cin>>T;
    while(T--) {
        cin>>a>>b>>c>>d>>k;
        cout<<work(b/k,d/k)-work((a-1)/k,d/k)-work(b/k,(c-1)/k)+work((a-1)/k,(c-1)/k)<<'\n'; 
    }
    return 0;
}