题解

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
const int N = 45000;

vector<int> get_primes(int x) {
vector<int> primes;
vector<bool> st(x + 1);
for (int i = 2; i <= x; i++) {
if (!st[i]) {
primes.push_back(i);
}
for (int j = 0; j < primes.size() && primes[j] <= x / i; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0)
break;
}
}
return primes;
}

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

void dfs(int u, int p, const vector<PII>& factor, vector<int>& divider) {
if (u >= factor.size()) {
divider.push_back(p);
return;
}
int power = factor[u].second;
int factorVal = factor[u].first;
for (int i = 0; i <= power; i++) {
dfs(u + 1, p, factor, divider);
p *= factorVal;
}
}

int main() {
vector<int> primes = get_primes(N);
int t;
scanf("%d", &t);
while (t--) {
int a0, a1, b0, b1;
scanf("%d %d %d %d", &a0, &a1, &b0, &b1);

int num = b1;
vector<PII> factor;
for (int i = 0; i < primes.size() && primes[i] <= num / primes[i]; i++) {
    if (num % primes[i] == 0) {
        int power = 0;
        while (num % primes[i] == 0) {
            num /= primes[i];
            power++;
        }
        factor.emplace_back(primes[i], power);
    }
}
if (num > 1) {
    factor.emplace_back(num, 1);
}

vector<int> divider;
dfs(0, 1, factor, divider);

int ans = 0;
for (int i = 0; i < divider.size(); i++) {
    int x = divider[i];
    if (gcd(x, a0) == a1 && (LL)x * b0 / gcd(x, b0) == b1) {
        ans++;
    }
}

printf("%d\n", ans);

}
return 0;
}