分析

• 给定我们a、b、c、d，让我们求解有多少x，使得(a, x) = b, [c, x] = d，其中(a, x)表示两者的最大公约数，[c, x]表示两者的最小公约数。

• 我们可以直接枚举d的所有约数x，判断上述的两个式子是否成立即可。即是否有gcd(a, x) == b，且[c, x] == d，其中$[c, x] = \frac{c \times x}{gcd(c, x)}$。我们需要考虑如何枚举d的所有约数，最坏情况下，d取$2 \times 10 ^ 9$，一共有T=2000组数据，因此计算量为$T \times \sqrt{d} \approx 2 \times 10 ^ 3 \times 5 \times 10 ^ 4 = 10 ^ 8$，这样做很有可能会超时，因此不可取。

• 那么我们应该如何求出d的所有约数呢？我们可以采用分解质因数+DFS的方式求解。

• 分解质因数最普通的方式时间复杂度是$O(n)$的，可以参考：网址。这里采用另一种方式分解质因数：即先筛出1~50000之间的所有质数（因为$50000^2 > 2 \times 10 ^ 9$），然后我们遍历所有的质数，按照分解质数的方式求解即可。

• 筛质数只需要一次即可，因为只遍历质数，所以对于d进行质因子分解的时间复杂度为$O(\frac{d}{ln(d)})$，因此总体时间复杂度为$O(T \times \frac{d}{ln(d)})$。

代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 50010;  // 筛出1~N-1中所有的质数

int primes[N], cnt;
bool st[N];

struct Factor {
    int p, s;  // 质因子, 出现次数
} factor[10];  // int范围内的数据不同的质因子最多有9位
int fcnt;  // 某个数(分析中的d)的质因子个数

int dividor[1601];  // int范围内的数据不同的约数最多为1600个
int dcnt;  // 某个数(分析中的d)的约数的个数

// 筛质数
void init(int n) {

    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

// 根据质因子factor求解约数dividor
// u: 当前遍历到factor[u]
// p: 当前约数的值
void dfs(int u, int p) {

    if (u == fcnt) {
        dividor[dcnt++] = p;
        return;
    }

    for (int i = 0; i <= factor[u].s; i++) {
        dfs(u + 1, p);
        p *= factor[u].p;
    }
}

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int main() {

    // 筛质数
    init(N - 1);

    int T;
    cin >> T;
    while (T--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        // 质因数分解, 不是从2一直遍历到n/i, 而是只遍历质数
        fcnt = 0;
        int t = d;
        for (int i = 0; primes[i] <= t / primes[i]; i++) {
            int p = primes[i];
            if (t % p == 0) {
                int s = 0;
                while (t % p == 0) t /= p, s++;
                factor[fcnt++] = {p, s};
            }
        }
        if (t > 1) factor[fcnt++] = {t, 1};

        // 根据质因子factor求解约数dividor
        dcnt = 0;
        dfs(0, 1);

        // 此时d的所有约数都已经求出来了, 验证是否成立即可
        int res = 0;
        for (int i = 0; i < dcnt; i++) {
            int x = dividor[i];
            if (gcd(a, x) == b && (LL)c * x / gcd(c, x) == d) res++;
        }

        cout << res << endl;
    }

    return 0;
}