记录编号	386074	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题B	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	6.257 s
提交时间	2017-03-23 15:08:34	内存使用	0.91 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cstdarg>
#include <bitset>
using namespace std;
#define MAXN 50003
#define MAXP 50000
typedef long long LL;
int pm[MAXN], tot; LL miu[MAXN];
bool vis[MAXN];
void pre(){
	miu[1] = 1;
	for(int i = 2; i <= MAXP; i++){
		if(!vis[i]){
			pm[tot++] = i;
			miu[i] = -1;
		}
		for(int j = 0; j < tot; j++){
			int k = i*pm[j];
			if(k > MAXP)break;
			vis[k] = true;
			if(i%pm[j])miu[k] = -miu[i];
			else break;
		}
	}
	for(int i = 1; i <= MAXP; i++)
		miu[i] += miu[i-1];
} 
LL calc(int n, int m){
	if(n > m)swap(n, m);
	LL ans = 0;
	for(int i = 1, j; i <= n; i = j+1){
		j = min(n/(n/i), m/(m/i));
		ans += (miu[j]-miu[i-1])*(n/i)*(m/i); 
	} 
	return ans; 
} 
int main(){
	freopen("b.in", "r", stdin);
	freopen("b.out", "w", stdout);
	pre();	
	int T; scanf("%d", &T);
	while(T--){
		int a, b, x, y, d;
		scanf("%d %d %d %d %d", &a, &b, &x, &y, &d);
		LL ans = 0;
		ans += calc(b/d, y/d);
		ans -= calc((a-1)/d, y/d);
		ans -= calc(b/d, (x-1)/d);
		ans += calc((a-1)/d, (x-1)/d);
		printf("%lld\n", ans);
	}	
	return 0;
}