记录编号	157793	评测结果	AAAAAAAAAA
题目名称	[HAOI 2011]问题B	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	3.591 s
提交时间	2015-04-10 11:32:21	内存使用	0.51 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define getc() getchar()
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout))
template<class T>inline void getd(T &x){
    char ch = getc();bool neg = false;
    while(!isdigit(ch) && ch != '-')ch = getc();
    if(ch == '-')ch = getc(), neg = true;
    x = ch - '0';
    while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
    if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 50003;
int Mer[maxn] = {0, 1};

inline void Sieve(){
	int Pri[maxn], pcnt = 0, i, j, t;bool not_p[maxn] = {0};
	for(i = 2;i < maxn;++i){
		if(!not_p[i])Pri[pcnt++] = i, Mer[i] = -1;
		for(j = 0;j < pcnt;++j){
			if((t = i * Pri[j]) >= maxn)break;
			not_p[t] = true;
			if(i % Pri[j] == 0){
				Mer[t] = 0;
				break;
			}
			Mer[t] = Mer[i] * Mer[Pri[j]];
		}
	}
	for(i = 2;i < maxn;++i)Mer[i] += Mer[i-1];
}

int A, B, C, D, pts[4000], ptcnt;

inline void getpts(int t, int *pttmp, int &tmpcnt){//关键点:使t / d发生变化的前一个d
	int d, t_d, last = 0, tmp;
	if(t == 1){pttmp[tmpcnt++] = 1;return;}
	for(d = 2;d * d <= t;++d)if((tmp = t / d) != last){
		last = tmp;
		pttmp[tmpcnt++] = d - 1;
	}
	for(t_d = d;t_d;--t_d)if((tmp = t / t_d) != pttmp[tmpcnt-1])
		pttmp[tmpcnt++] = tmp;
}
#define under(i) (it[i] < tcnt[i])
#define conti (under(0) || under(1) || under(2) || under(3))
inline void work(){
	int Ans = 0, a, b, c, d, k, Min = maxn, tcnt[4] = {0};
	static int ptmp[4][1000];
	ptcnt = 0;
	getd(a), getd(b), getd(c), getd(d), getd(k);
	A = (a-1) / k, B = b / k, C = (c-1) / k, D = d / k;
	getpts(A,ptmp[0],tcnt[0]);getpts(B,ptmp[1],tcnt[1]);
	getpts(C,ptmp[2],tcnt[2]);getpts(D,ptmp[3],tcnt[3]);
	int it[4] = {0}, last = 0, i, t, tmp;
	while(conti){
		Min = maxn, i = -1;
		while(++i < 4)if(under(i)){
			while(under(i) && ptmp[i][it[i]] == last)++it[i];
			if(under(i) && (tmp = ptmp[i][it[i]]) < Min)
				Min = tmp, t = i;
		}
		if(Min < maxn)last = pts[ptcnt++] = Min;
	}
	int lastMer = 0;
	for(i = 0;i < ptcnt;++i){
		a = pts[i];
		Ans += (Mer[a] - lastMer) * (B / a - A / a) * (D / a - C / a);
		lastMer = Mer[a];
	}
	printf("%d\n", Ans);
}

int main(){
	#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#else
	SetFile(b);
	#endif
	
	Sieve();int N;getd(N);
	while(N--)work();
 
#ifdef DEBUG
    printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}