记录编号	220527	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题B	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	4.470 s
提交时间	2016-01-18 20:30:36	内存使用	0.93 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int sum[50010];
int mu[50010];
bool b[50010];
int q[50010],w;
int aa,bb,cc,dd,kk;
inline void gycl()
{
	mu[1]=1;
	for(int i=2;i<=50000;i++)
	{
		if(!b[i])
		{
			q[++w]=i;
			mu[i]=-1;
		}
		for(int j=1;i*q[j]<=50000&&j<=w;j++)
		{
			b[q[j]*i]=1;
			if(i%q[j]==0)
			{
				mu[i*q[j]]=0;
				break;
			}
			mu[i*q[j]]=-mu[i];
		}
	}
	for(int i=1;i<=50000;i++)		
		sum[i]=sum[i-1]+mu[i];
}
inline int g(int m,int n)
{
	if(n>m)
		swap(m,n);
	int ls=0;
	int re=0;
	for(int i=1;i<=n;i=ls+1)
	{
		ls=min(n/(n/i),m/(m/i));
		re+=(n/i)*(m/i)*(sum[ls]-sum[i-1]);
	}
	return re;
}
inline void gmain()
{
	scanf("%d%d%d%d%d",&aa,&bb,&cc,&dd,&kk);
	printf("%d\n",g(dd/kk,bb/kk)-g((aa-1)/kk,dd/kk)-g(bb/kk,(cc-1)/kk)+g((aa-1)/kk,(cc-1)/kk));
}
int main()
{
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	int n;
	gycl();
	scanf("%d",&n);
	while(n--)
		gmain();
}