记录编号	220296	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题B	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	4.753 s
提交时间	2016-01-17 20:32:40	内存使用	0.73 MiB

#include<cstdio>
inline int MIN(int A,int B){return A<B?A:B;}
int T,a,b,c,d,k;
int mu[51000],prime[51000];
bool flag[51000];
void get_mu(int x)
{
	mu[1]=1;
	for(int i=2;i<x;++i)
	{
		if(!flag[i])
		{
			prime[++prime[0]]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=prime[0]&&i*prime[j]<x;++j)
		{
			flag[i*prime[j]]=1;
			if(i%prime[j])
				mu[i*prime[j]]=-mu[i];
			else
			{
				mu[i*prime[j]]=0;
				break;
			}
		}
	}
	for(int i=2;i<x;++i)
		mu[i]+=mu[i-1];
}
inline int ans(int n,int m)
{
	int end=0,last;
	for(int i=1;i<=n&&i<=m;i=last+1)
	{
		last=MIN(n/(n/i),m/(m/i));
		end+=(n/i)*(m/i)*(mu[last]-mu[i-1]);		
	}
	return end;
}
int main()
{
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	get_mu(51000);
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		printf("%d\n",ans(b/k,d/k)-ans((a-1)/k,d/k)-ans(b/k,(c-1)/k)+ans((a-1)/k,(c-1)/k));
	}
}