记录编号	234108	评测结果	AAAAAAAAAA
题目名称	[NOIP 2009]Hankson的趣味题	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.453 s
提交时间	2016-03-06 20:21:50	内存使用	0.31 MiB

//KZNS
#include <fstream>
#include <vector>
#include <utility>
using namespace std;
//
ifstream fin ("son.in");
ofstream fout ("son.out"); 
typedef pair<int, int> poi;
//
class poo {
public:
	int d, s, w;
};
//
poo make_poo(int d, int s, int w) {
	poo u;
	u.d=d;
	u.s=s;
	u.w=w;
	return u;
}
//
int main() {
	vector<int> vv;
	bool f;
	for (int i=2; i<44723; i++) {
		f=true;
		for (int j=0; f&&j<vv.size(); j++) {
			if (i%vv[j]==0)
				f=false;
		}
		if (f)
			vv.push_back(i);
	}
	int n;
	fin >>n;
	vector<poi> va0, va1, vb0 ,vb1;
	int a0, a1, b0, b1;
	while (n--) {
		va0.clear();
		va1.clear();
		vb0.clear();
		vb1.clear();
		fin >>a0 >>a1 >>b0 >>b1;
		for (int i=0; i<vv.size()&&vv[i]<=a0; i++) {
			int j=0;
			while (a0%vv[i]==0) {
				a0/=vv[i];
				j++;
			}
			if (j) {
				va0.push_back(make_pair(vv[i], j));
			}
		} 
		if (a0>1)
			va0.push_back(make_pair(a0, 1));
		for (int i=0; i<vv.size()&&vv[i]<=a1; i++) {
			int j=0;
			while (a1%vv[i]==0) {
				a1/=vv[i];
				j++;
			}
			if (j) {
				va1.push_back(make_pair(vv[i], j));
			}
		}
		if (a1>1)
			va1.push_back(make_pair(a1, 1));
		for (int i=0; i<vv.size()&&vv[i]<=b0; i++) {
			int j=0;
			while (b0%vv[i]==0) {
				b0/=vv[i];
				j++;
			}
			if (j) {
				vb0.push_back(make_pair(vv[i], j));
			}
		}
		if (b0>1)
			vb0.push_back(make_pair(b0, 1));
		for (int i=0; i<vv.size()&&vv[i]<=b1; i++) {
			int j=0;
			while (b1%vv[i]==0) {
				b1/=vv[i];
				j++;
			}
			if (j) {
				vb1.push_back(make_pair(vv[i], j));
			}
		}
		if (b1>1)
			vb1.push_back(make_pair(b1, 1));
		int a0i=0, a1i=0, b0i=0, b1i=0;
		vector<poo> va, vb;
		for (; a0i<va0.size(); a0i++) {
			while (a1i<va1.size()&&va1[a1i].first<va0[a0i].first) {
				a1i++;
			}
			if (a1i==va1.size()) {
				break;
			}
			if (va1[a1i].first==va0[a0i].first) {
				if (va1[a1i].second==va0[a0i].second) {
					va.push_back(make_poo(va0[a0i].first, va1[a1i].second, 0x7fffffff));
				}
				else {
					va.push_back(make_poo(va0[a0i].first, va1[a1i].second, va1[a1i].second));
				}
			}
			else {
				va.push_back(make_poo(va0[a0i].first, 0, 0));
			}
		}
		for (; a0i<va0.size(); a0i++) {
			va.push_back(make_poo(va0[a0i].first, 0, 0));
		}
		for (; b1i<vb1.size(); b1i++) {
			while (b0i<vb0.size()&&vb0[b0i].first<vb1[b1i].first) {
				b0i++;
			}
			if (b0i==vb0.size()) {
				break;
			}
			if (vb0[b0i].first==vb1[b1i].first) {
				if (vb0[b0i].second==vb1[b1i].second) {
					vb.push_back(make_poo(vb1[b1i].first, 0, vb1[b1i].second));
				}
				else {
					vb.push_back(make_poo(vb1[b1i].first, vb1[b1i].second, vb1[b1i].second));
				}
			}
			else {
				vb.push_back(make_poo(vb1[b1i].first, vb1[b1i].second, vb1[b1i].second));
			}
		}
		for (; b1i<vb1.size(); b1i++) {
			vb.push_back(make_poo(vb1[b1i].first, vb1[b1i].second, vb1[b1i].second));
		}
		int ed=1;
		int aa=0, bb=0;
		int w, s;
		while (aa<va.size()&&bb<vb.size()) {
			if (va[aa].d==vb[bb].d) {
				w=min(va[aa].w, vb[bb].w);
				s=max(va[aa].s, vb[bb].s);
				if (s<=w) {
					ed*=w-s+1;
				}
				else {
					ed=0;
					goto efor;
				}
				aa++;
				bb++;
			}
			else if (va[aa].d<vb[bb].d) {
				w=min(va[aa].w, 0);
				s=max(va[aa].s, 0);
				if (s<=w) {
					ed*=w-s+1;
				}
				else {
					ed=0;
					goto efor;
				}
				aa++;
			}
			else {
				w=min(0x7fffffff, vb[bb].w);
				s=max(0, vb[bb].s);
				if (s<=w) {
					ed*=w-s+1;
				}
				else {
					ed=0;
					goto efor;
				}
				bb++;
			}
		}
		while (bb<vb.size()) {
			w=min(0x7fffffff, vb[bb].w);
			s=max(0, vb[bb].s);
			if (s<=w) {
				ed*=w-s+1;
			}
			else {
				ed=0;
				goto efor;
			}
			bb++;
		}
		while (aa<va.size()) {
			w=min(va[aa].w, 0);
			s=max(va[aa].s, 0);
			if (s<=w) {
				ed*=w-s+1;
			}
			else {
				ed=0;
				goto efor;
			}
			aa++;
		}
		efor:
		fout <<ed <<endl;
	}
	return 0;
}
//UBWH