记录编号	357558	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题B	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	5.090 s
提交时间	2016-12-11 15:16:56	内存使用	2.02 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=55000;
#define LL long long
#define Begin freopen("b.in","r",stdin);freopen("b.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
bool vis[maxn];
int Prime[maxn],mu[maxn],tot,sum[maxn];
int a[maxn],b[maxn],c[maxn],d[maxn],k[maxn],till;
void Init();
void Get_mu(){
	mu[1]=1;
	for(int i=2;i<=till;i++){
		if(!vis[i]){
			Prime[++tot]=i;mu[i]=-1;
		}
		for(int j=1;j<=tot;j++){
			if(i*Prime[j]>till)break;
			vis[i*Prime[j]]=true;
			if(i%Prime[j]==0)break;
			mu[i*Prime[j]]=-mu[i];
		}
	}
}
LL calc(int n,int m,int z){
	n/=z;m/=z;if(n>m)swap(n,m);
	LL ans=0;int last;
	for(int i=1;i<=n;i=last+1){
		last=min(n/(n/i),m/(m/i));
		ans+=1ll*(n/i)*(m/i)*(sum[last]-sum[i-1]);
	}
	return ans;
}
int main(){
	Begin;
	int T=0;scanf("%d",&T);
	for(int i=1;i<=T;i++){
		scanf("%d%d%d%d%d",&a[i],&b[i],&c[i],&d[i],&k[i]);
		till=max(till,max(b[i],d[i]));
	}
	Get_mu();
	for(int i=1;i<=till;i++)sum[i]=sum[i-1]+mu[i];
	for(int i=1;i<=T;i++)printf("%lld\n",calc(b[i],d[i],k[i])-calc(a[i]-1,d[i],k[i])-calc(b[i],c[i]-1,k[i])+calc(a[i]-1,c[i]-1,k[i]));
    getchar();getchar();
    return 0;
}