题目相关

题目链接：洛谷 P2522 [HAOI2011]Problem b

题目描述：

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

输入输出格式：

输入格式：
第一行一个整数 $n$ ，接下来 $n$ 行每行五个整数，分别表示 $a、b、c、d、k$ 。
输出格式：
共 $n$ 行，每行一个整数表示满足要求的数对 $(x,y)$ 的个数。

输入输出样例：

输入#1	输出#1
2 2 5 1 5 1 1 5 1 5 2	14 3

说明：

100%的数据满足：$1≤n≤50000$ ， $1≤a≤b≤50000$ ， $1≤c≤d≤50000$ ， $1≤k≤50000$ 。

博主乱搞

蒟蒻解析：

看到 $gcd$ 果断想一想是不是和某个神奇的反演搞上了？（本来做做这道题就是来复习一下的。。。）
我们知道莫比乌斯反演有两个式子：（蒟蒻博主默默标记一下小|大）

$$F(n)=\sum\limits_{d|n}^{}{f(d)}\Longrightarrow f(n)=\sum\limits_{d|n}^{}{\mu(d)F{(\frac{n}{d}})}$$

$$F(n)=\sum\limits_{n|d}^{}{f(d)}\Longrightarrow f(n)=\sum\limits_{n|d}^{}{\mu (\frac{d}{n})F{(d)}}$$

第一个式子一般用于枚举因数，第二个用来枚举倍数。这里我们用第二种。
设 $f(k)$ 代表 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}{[gcd(i,j)==k]}$ 的个数， $F(k)$ 代表 $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}{[gcd(i,j)==k及其倍数]}$ 。显然， $F(k)=\sum\limits_{n|d}^{}{f(d)}$ ，则 $f(k)=\sum\limits_{k|d}^{}{\mu (\frac{d}{k})F{(d)}}$ 。又因为 $F(k)=\lfloor \frac{n}{k} \rfloor \lfloor \frac{m}{k} \rfloor$ ,所以就能够求出 $f(k)$ 。为了方便，我们最后一班把 $gcd(i,j)==k$ 的形式转化为 $gcd(i,j)==1$ 的形式便于计算。
至于最终答案，我们可以利用二维前缀和知识进行相关转化。设方程中求和的 $m,n$ 给出，结果为 $calc(m,n)$ ，则最终答案为 $Ans=calc(b,d)-calc(a-1,d)-calc(b,c-1)+calc(a-1,c-1)$ 。
由于有多组询问我们就可以分块解决。

蒟蒻代码：

cpp

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long 
#define il inline 
il int read(){
	int x=0,f=1; char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1; ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0'; ch=getchar();
	}
	return x*f;
}
const int maxn=50010;
int prime[maxn],tot;
bool notprime[maxn];
int mu[maxn],sum[maxn];
void get_mu(){
	notprime[1]=true; mu[1]=1;
	for (int i=2;i<=50000;++i){
		if (!notprime[i]){
			prime[++tot]=i;
			mu[i]=-1;
		}
		for (int j=1;j<=tot&&i*prime[j]<=50000;++j){
			notprime[i*prime[j]]=true;
			if (i%prime[j]==0) break;
			else mu[i*prime[j]]=-mu[i];
		}
	}
	for (int i=1;i<=50000;++i){
		sum[i]=sum[i-1]+mu[i];
	}
}
int t;
int a,b,c,d,k;
ll ans;
il ll calc(int x,int y){
	ll tmp=0;
	int mx=min(x,y)/k;
	for (int l=1,r;l<=mx;l=r+1){
		r=min(x/(x/l),y/(y/l));
		tmp+=(ll)(x/(l*k))*(ll)(y/(l*k))*(sum[r]-sum[l-1]);
	}
	return tmp;
}
int main(){
	t=read(); get_mu();
	while (t--){
		ans=0;
		a=read(); b=read(); c=read(); d=read(); k=read();
		ans+=calc(b,d)-calc(a-1,d)-calc(b,c-1)+calc(a-1,c-1);
		printf("%lld\n",ans);
	}
	return 0;
}