记录编号	42382	评测结果	AAAAAAAAAA
题目名称	405.[NOIP 2009]Hankson的趣味题	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.024 s
提交时间	2012-09-21 09:22:55	内存使用	1.72 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 50000;
int p[N], m;
void prime() {
    bool l[N] = {0};
    for(int i=2; i<N; i++)
        if(!l[i]) {
            p[m++] = i;
            for(int j=i; j<N; j+=i)
                l[j] = 1;
        }
}
int n, s, l, r;
int a[2], b[2], x[2], y[2];
int main() {
    freopen("son.in", "r", stdin);
    freopen("son.out", "w", stdout);
    prime();
    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        scanf("%d %d", a, a+1);
        scanf("%d %d", b, b+1);
        s = 1;
        for(int j=0; p[j]*p[j]<=b[1]; j++)
            if(b[1] % p[j] == 0) {
                x[0] = x[1] = y[0] = y[1] = 0;
                for(; a[0] % p[j] == 0; x[0]++) a[0] /= p[j];
                for(; a[1] % p[j] == 0; x[1]++) a[1] /= p[j];
                for(; b[0] % p[j] == 0; y[0]++) b[0] /= p[j];
                for(; b[1] % p[j] == 0; y[1]++) b[1] /= p[j];
                l = x[1]; r = m;
                if(x[0] > x[1]) r = x[1];
                if(y[0] < y[1]) {
                    if(y[1] > r || l > r) s = 0;
                    l = r = y[1];
                } else r = min(r, y[1]);
                s *= r - l + 1;
            }
        if(a[1] > 1 && a[1] != b[1]) s = 0;
        if(a[0] > 1 && a[0] != a[1] && b[1] == a[0] && b[0] != a[0]) s = 0;
        if(b[1] > 1 && b[0] > 1 && a[1] != b[1] && a[0] % b[1]) s *= 2;
        printf("%d\n", s);
    }
    return 0;
}