使用容斥原理，只需计算 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m[\gcd(i,j)=k]$。

同时除以 $k$，即 $\sum\limits_{i=1}^{\left\lfloor\frac nk\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac mk\right\rfloor}[gcd(i,j)=1]$。

根据莫比乌斯函数的定义，上式等于 $\sum\limits_{i=1}^{\left\lfloor\frac nk\right\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac mk\right\rfloor}\sum\limits_{d|\gcd(i,j)}\mu(d)$。

调换枚举顺序可得 $\sum\limits_{d=1}^n\sum\limits_{i=1}^{\left\lfloor\frac n{dk}\right\rfloor}\sum\limits_{i=1}^{\left\lfloor\frac m{dk}\right\rfloor}\mu(d)=\sum\limits_{d=1}^n\mu(d)\cdot\left\lfloor\frac n{dk}\right\rfloor\left\lfloor\frac m{dk}\right\rfloor$。

预处理 $\mu$ 函数的前缀和，对 $\left\lfloor\frac n{dk}\right\rfloor\left\lfloor\frac m{dk}\right\rfloor$ 的值整除分块计算即可。

时间复杂度 $O(\sum\sqrt{nm})$。

/* 
 * @date: 2024.01.10
 * @problem: P7215
 * @algo: 莫比乌斯函数
 */

#include<bits/stdc++.h>
using namespace std;

bool vis[50001];
int mu[50001],cntPrime,prime[50001];

void calcMu(int n=50000){
    mu[1]=1;
    for(int i=2;i<=n;i++){
        if(!vis[i])prime[++cntPrime]=i,mu[i]=-1;
        for(int j=1;j<=cntPrime&&i*prime[j]<=n;j++){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=2;i<=n;i++)mu[i]+=mu[i-1];
}

int solve(int n,int m,int k){
    int sum=0;
    for(int l=1,r;n/(l*k)&&m/(l*k);l=r+1){
        r=min(n/k/(n/(l*k)),m/k/(m/(l*k)));
        sum+=(mu[r]-mu[l-1])*(n/(l*k))*(m/(l*k));
    }
    return sum;
}

int main(){
    calcMu();
    int T; scanf("%d",&T);
    while(T--){
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        printf("%d\n",solve(b,d,k)-solve(a-1,d,k)-solve(b,c-1,k)+solve(a-1,c-1,k));
    }
    return 0;
}

Problem b

link

做法：莫比乌斯反演。

思路：

对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$，满足 $a \le x \le b$，$c \le y \le d$，且 $\gcd(x,y) = k$，$\gcd(x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。 我们设

$$\operatorname{f}(n)=\sum\limits_{i=1}^x \sum\limits_{j=1}^y [n|\gcd(i,j)] $$$$ans=\operatorname{g}(n)=\sum\limits_{i=1}^x \sum\limits_{j=1}^y [\gcd(x,y)=k] $$

利用容斥原理，答案为图像上蓝色部分：

问题在于如何求 $\operatorname{g}(x,y)$ 。

我们知道：

$$\operatorname{f}(n)=\sum\limits_{n|d}\operatorname{g}(d) $$

利用莫比乌斯反演可得：

$$\operatorname{g}(n)=\sum\limits_{n|d}\operatorname{\mu}(\frac{d}{n})\operatorname{f}(n) $$

$\operatorname{\mu}(\frac{d}{n})$ 可以利用线性筛求出， $\operatorname{f}(d)$ 易得 $\operatorname{f}(d)=\left\lfloor\frac{x}{n}\right\rfloor \left\lfloor\frac{y}{n}\right\rfloor$

答案可以推出：

$$ans=\sum\limits_{n|d}\operatorname{\mu}(\frac{d}{n})\operatorname{f}(d)=\sum\limits_{i=1}^{\min(x,y)}\operatorname{\mu}(i)\left\lfloor\frac{x}{i\cdot n}\right\rfloor \left\lfloor\frac{y}{i\cdot n}\right\rfloor $$

再利用数论分块以及前缀和优化一下就不会超时了。

代码：

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<algorithm>
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{
    typedef __uint128_t ULLL;
    static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    inline void pc(const char &ch){
    	if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
    	*pw++=ch;
	}
    #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
	struct FastMod{
        FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){}
        ULL reduce(ULL a){
            ULL q=(ULL)((ULLL(m)*a)>>64);
            ULL r=a-q*b;
            return r>=b?r-b:r;
        }
        ULL b,m;
    }HPOP(10);
    struct QIO{
    	char ch;
    	int st[40];
    	template<class T>inline void read(T &x){
    		x=0,ch=gc;
    		while(!isdigit(ch))ch=gc;
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
		}
		template<class T>inline void write(T a){
			do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
			pc('\n');
		}
	}qrw;
}
using namespace FastIo;
#define P(A) A=-~A
#define fione(i,a,b) for(register int i=a;i<=b;P(i))
const int NUMBER1=5e4;
int prime[NUMBER1+5],cnt(0);
LL mu[NUMBER1+5];
bool pd[NUMBER1+5];
inline void PRIME(){
	int k;
	mu[1]=1;
	fione(i,2,NUMBER1){
		if(!pd[i])prime[++cnt]=i,mu[i]=-1;
		for(register int j(1);prime[j]*i<=NUMBER1;P(j)){
			k=prime[j]*i;
			pd[k]=true;	
			if(!(i%prime[j]))break;
			mu[k]-=mu[i];
		}
	}
	fione(i,1,NUMBER1)mu[i]+=mu[i-1];
}
inline int fk(int k,int x){return k/(k/x);}
inline LL work(int x,int y,int k){
	x/=k,y/=k;
	LL ans(0);int n=std::min(x,y);
	for(register int l=1,r;l<=n;l=r+1){
		r=std::min(n,std::min(fk(x,l),fk(y,l)));
		ans+=(mu[r]-mu[l-1])*(x/l)*(y/l);
	}
	return ans;
}
signed main(){
	PRIME();
	int T,a,b,c,d,k;
	qrw.read(T);
	while(T--){
		qrw.read(a);
		qrw.read(b);
		qrw.read(c);
		qrw.read(d);
		qrw.read(k);
		qrw.write(work(b,d,k)-work(a-1,d,k)-work(b,c-1,k)+work(a-1,c-1,k));
	}
	fsh;
    exit(0);
    return 0;
}