记录编号	158150	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题B	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	4.757 s
提交时间	2015-04-12 22:47:53	内存使用	0.59 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============

///==============var declaration=================
const int MAXN=50050;
int a,b,c,d,prime_cnt=0;
int mu[MAXN],prime[MAXN];
bool isprime[MAXN];
///==============function declaration============
void GetPrime();
inline int Query(int L,int R);
///==============main code=======================
int main()
{


   freopen("b.in","r",stdin);
   freopen("b.out","w",stdout);

	int T;
	scanf("%d",&T);
	GetPrime();
	while (T--){
		int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		int res1=Query((a-1)/k,(c-1)/k);
		int res2=Query(b/k,d/k);
		int res3=Query(b/k,(c-1)/k);
		int res4=Query((a-1)/k,d/k);
		printf("%d\n",res1+res2-res3-res4);
	}	
   return 0;
}
///================fuction code====================
void GetPrime(){
	memset(isprime,true,sizeof(isprime));
	mu[1]=1;prime_cnt=0;
	for(int i=2;i<=50000;i++){
		if (isprime[i]){
			mu[i]=-1;
			prime[++prime_cnt]=i;
		}
		for(int j=1;j<=prime_cnt&&i*prime[j]<=50000;j++){
			isprime[i*prime[j]]=false;
			if (i%prime[j]!=0)
				mu[i*prime[j]]=-mu[i];
			else{
				mu[i*prime[j]]=0;
				break;
			}
		}
	}
	for(int i=1;i<=50000;i++)
		mu[i]+=mu[i-1];
}
inline int Query(int n,int m){
	if (n>m) swap(n,m);
	int next,res=0;
	for(int i=1;i<=n;i=next+1){
		next=min(n/(n/i),m/(m/i));
		res+=(long long)(n/i)*(long long)(m/i)*(long long)(mu[next]-mu[i-1]);
	}
	return res;
}