题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2301

题目分类：数论，莫比乌斯反演

题意：

n个询问，每次询问有多少个数对(x,y)满足a<=x<=b且c<=y<=d且gcd(x,y)=k

题解：

使用容斥原理可以将问题转化成bzoj 1101这道题【f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)】

然后可以将问题转化成互质的数

可以通过一系列变换将式子转化为可以分块的式子

具体详见http://hzwer.com/4205.html

程序：

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
long long n,x1,x2,x3,x4,m;
long long miu[70000],isp[70000],cnt,pri[70000],summ[70000];
inline void shai()
{
	miu[1]=1;
	for (long long i=2;i<=60000;i++)
	{
		if(isp[i]==0){cnt++;pri[cnt]=i;miu[i]=-1;}
		for (long long j=1;j<=cnt&&i*pri[j]<=60000;j++)
		{
			isp[i*pri[j]]=1;
			if(i%pri[j]==0){miu[i*pri[j]]=0;break;}
			else miu[i*pri[j]]=-miu[i];
		}
	}
	for (long long i=1;i<=60000;i++)
	{
		summ[i]=summ[i-1]+miu[i];
	}
}
inline long long query(long long x,long long y)
{
	if(x>y)swap(x,y);
	long long pos=0,i=1,ans=0;
	while (i<=x)
	{
		pos=min(x/(x/i),y/(y/i));
		ans+=(summ[pos]-summ[i-1])*(x/i)*(y/i);
		i=pos+1;
	}//printf("%lld %lld %lld\n",x,y,ans);
	return ans;
}
int main()
{
	shai();
	scanf("%lld",&n);
	while (n--)
	{
		scanf("%lld %lld %lld %lld %lld",&x1,&x2,&x3,&x4,&m);
		x1--;x3--;
		printf("%lld\n",query(x2/m,x4/m)+query(x1/m,x3/m)-query(x1/m,x4/m)-query(x2/m,x3/m));
	}
	return 0;
}