记录编号	54855	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题B	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	4.046 s
提交时间	2013-03-13 20:21:45	内存使用	0.89 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<deque>
using namespace std;
const int MAXN=50000+10;
int g[MAXN]={0};//容斥系数
void prime(void){
	bool p[MAXN]={0};//素数
	int i,j;
	for(i=1;i<=50000;i++) g[i]=1;
	for(i=2;i<=50000;i++){
		if(p[i]) continue;//如果是素数进入下面的内容
		g[i]=-1;
		for(j=2;j*i<=50000;j++){
			p[j*i]=true;//合数
			if(j%i==0) g[j*i]=0;
			else g[j*i]*=-1;			
		}
	}
	for(i=2;i<=50000;i++) g[i]+=g[i-1];//前缀和优化
}
int cria[MAXN]={0},crib[MAXN]={0};//分界点
int cna,cnb;//a和b的分界点的个数
void getcri(int a,int b){
	int i;
	cna=(int)sqrt((double)a)*2;
	for(i=1;i*i<=a;i++){
		cria[i]=i,cria[cna+1-i]=a/i;
	}
	cnb=(int)sqrt((double)b)*2;
	for(i=1;i*i<=b;i++){
		crib[i]=i,crib[cnb+1-i]=b/i;
	}
}
int calc(int a,int b,int k){
	a/=k,b/=k;
	getcri(a,b);
	int i,j;
	int ans=0,last;
	i=1,j=1,last=0;
	while(i<=cna||j<=cnb){
		if(i<=cna&&(j>cnb||cria[i]<crib[j])){
			ans+=(g[cria[i]]-g[last])*(a/cria[i])*(b/cria[i]);
			last=cria[i];
			i++;
		}
		else{
			ans+=(g[crib[j]]-g[last])*(a/crib[j])*(b/crib[j]);
			last=crib[j];
			j++;
		}
	}
	return ans;
}
int a,b,c,d,k;
void work(void){
	scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
	printf("%d\n",calc(b,d,k)-calc(b,c-1,k)-calc(a-1,d,k)+calc(a-1,c-1,k));
}
int main(){
	freopen("b.in","r",stdin);
	freopen("b.out","w",stdout);
	prime();
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) work();
	return 0; 
}