【HAOI 2011】Problem b / 题解

Description

给出 $n$ 个询问，每次询问有多少个数对 $(x,y)$ 满足 $a\leq x\leq b, c\leq y \leq d$，且 $gcd(x,y)=k$。

Idea

首先我们可以差分一下，求下面这个函数的值。

$$f(k)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]$$

我们设

$$F(k)=\sum\limits_{k|d}f(d)(d<=\min(n,m))$$

表示所有公约数为 $k$ 的倍数 $d$ 的答案个数。

根据莫比乌斯反演，

$$f(k)=\sum\limits_{k|d}\mu(\lfloor\frac{d}{k}\rfloor)F(d)$$

枚举 $x=\lfloor\frac{d}{k}\rfloor$，化为

$$\begin{aligned}f(k)=&\sum\limits_{x=1}^{\min(\frac{n}{k},\frac{m}{k})}\mu(x)F(xk) \\ =& \sum\limits_{x=1}^{\min(\frac{n}{k},\frac{m}{k})}\mu(x) \lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{xk}\rfloor\end{aligned}$$

对 $\mu(x)$ 求前缀和，分块处理即可。

Code

#include <bits/stdc++.h>
#define maxn 50010
#define min(a,b) (a<b?a:b)
#define ll long long
int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch-'0'),ch=getchar();
    return x;
}
bool vis[maxn];
int mu[maxn],pri[maxn],top;
int sum[maxn];
void init(int n){
    mu[1]=1;
    for (int i=2;i<=n;++i){
        if (!vis[i])pri[++top]=i,mu[i]=-1;
        for (int j=1;j<=top&&i*pri[j]<=n;++j){
            vis[i*pri[j]]=1;
            if (i%pri[j]) mu[i*pri[j]]=-mu[i];
            else break;
        }
    }
    for (int i=1;i<=n;++i)
        sum[i]=sum[i-1]+mu[i];
}
ll calc(int n,int m,int k){
    if (n>m) std::swap(n,m);
    ll res=0;
    int d=n/k;
    for (int l=1,r;l<=d;l=r+1){
        r=min((n/k)/(n/l/k),(m/k)/(m/l/k));
        res+=1ll*(sum[r]-sum[l-1])*(1ll*(n/l/k)*(m/l/k));
    }
    return res;
}
int main(){
    int T=read();init(maxn-1);
    for (int i=1;i<=T;++i){
        int a=read()-1,b=read(),c=read()-1,d=read(),k=read();
        printf("%lld\n",calc(b,d,k)-calc(a,d,k)-calc(b,c,k)+calc(a,c,k));
    }
}