阶段一：Hankson的趣味数学挑战——不使用辗转相除法求解特定条件下的正整数

Hanks博士的儿子Hankson最近遇到了一个数学难题。他在课堂上学到了如何计算两个正整数的最大公约数（GCD）和最小公倍数（LCM）。基于这些知识，Hankson提出了一个逆向问题：给定四个正整数a0, a1, b0, b1，求解一个正整数x，使得x和a0的最大公约数是a1，同时x和b0的最小公倍数是b1。

经过一番思考，Hankson意识到满足这些条件的x可能不唯一，甚至可能不存在。因此，他决定计算满足条件的x的个数。你的任务是编写一个程序来帮助Hankson解决这个问题。

输入格式

输入的第一行包含一个正整数n，表示有n组测试数据。接下来的n行每行包含四个正整数a0, a1, b0, b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。

输出格式

输出共n行，每组输入数据的输出结果占一行，为一个整数。对于每组数据：如果不存在满足条件的x，输出0；如果存在满足条件的x，输出满足条件的x的个数。

数据范围

1 ≤ n ≤ 2000
1 ≤ a0, a1, b0, b1 ≤ 2 × 10^9

示例

输入：
2
41 1 96 288
95 1 37 1776

输出：
6
2

解题思路

为了求解这个问题，我们可以将a0, a1, b0, b1分解为质因数的形式。假设质因数分解后：

a0 = x1^α1 * x2^α2 * ... * xn^αn
a1 = x1^β1 * x2^β2 * ... * xn^βn
b0 = x1^γ1 * x2^γ2 * ... * xn^γn
b1 = x1^δ1 * x2^δ2 * ... * xn^δn

我们需要找到一个正整数X，使得：

X = x1^ε1 * x2^ε2 * ... * xn^εn

根据题目条件，有：

βi = min(αi, εi) (i = 1, 2, ..., n)
δi = max(γi, εi) (i = 1, 2, ..., n)

通过上述关系，我们可以推导出εi的取值范围：

• 当βi = αi时，εi可以取大于等于αi的任意自然数。
• 当βi ≠ αi时，εi被固定为βi。
• 当δi = γi时，εi可以取小于等于γi的任意自然数。
• 当δi ≠ γi时，εi被固定为δi。
• 如果εi被固定成两个不同的数，则无解，输出0。

特别注意的是，由于X ≤ 2 × 10^9，我们只需要考虑小于等于√(2 × 10^9)的质因数。如果X有大于√(2 × 10^9)的质因数，那么这个质因数只能有一个。

代码实现

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
inline ll read() {
    char c = getchar();
    ll s = 0, f = 1;
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        s = s * 10 + c - '0';
        c = getchar();
    }
    return f * s;
}
ll a1, a2, b1, b2;
bool bk[51000000];
int tot, pri[4100];
inline void pre() {
    memset(bk, true, sizeof(bk));
    for (int i = 2; i <= 200000; i++) {
        if (bk[i]) pri[++tot] = i;
        if (tot > 4000) break;
        for (int j = 1; j <= tot && pri[j] * i <= 200000; j++) {
            bk[i * pri[j]] = false;
            if (i % pri[j] == 0) break;
        }
    }
}
ll ta1[4100], ta2[4100], tb1[4100], tb2[4100];
ll xia[4100], shang[4100];
int main() {
    // freopen("input10.in", "r", stdin);
    pre();
    int T = read();
    while (T--) {
        a1 = read();
        a2 = read();
        b1 = read();
        b2 = read();
        memset(ta1, 0, sizeof(ta1));
        memset(ta2, 0, sizeof(ta2));
        memset(tb1, 0, sizeof(tb1));
        memset(tb2, 0, sizeof(tb2));
        for (int i = 1; i <= tot; i++) {
            if (a1 == 1) break;
            while (a1 != 1 && a1 % pri[i] == 0) a1 /= pri[i], ta1[i]++;
        }
        for (int i = 1; i <= tot; i++) {
            if (a2 == 1) break;
            while (a2 != 1 && a2 % pri[i] == 0) a2 /= pri[i], ta2[i]++;
        }
        for (int i = 1; i <= tot; i++) {
            if (b1 == 1) break;
            while (b1 != 1 && b1 % pri[i] == 0) b1 /= pri[i], tb1[i]++;
        }
        for (int i = 1; i <= tot; i++) {
            if (b2 == 1) break;
            while (b2 != 1 && b2 % pri[i] == 0) b2 /= pri[i], tb2[i]++;
        }
        ll ans = 1;
        for (int i = 1; i <= tot; i++) {
            if (ta1[i] != ta2[i]) xia[i] = -1;
            else xia[i] = ta1[i];
            if (tb1[i] != tb2[i]) shang[i] = -1;
            else shang[i] = tb1[i];
            if (xia[i] == -1 && shang[i] == -1 && min(ta1[i], ta2[i]) != max(tb1[i], tb2[i])) {
                ans = 0;
                break;
            }
            if (xia[i] != -1 && shang[i] != -1)
                ans *= (shang[i] - xia[i] + 1);
        }
        if (a1 != 1 || a2 != 1 || b1 != 1 || b2 != 1) {
            if (b1 == b2 && b1 != 1) ans <<= 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}