超级简洁的做法

看到这篇题解之后立马 A 掉了，真的很简洁的一个做法。

我们有\(gcd(x,a_0)=a_1\)，根据结论\(gcd(a,b)=c \to gcd(\frac{a}{c},\frac{b}{c})=1\)，可以推出：

\[gcd(\frac{x}{a_1},\frac{a_0}{a_1})\]

另一个式子\(lcm(x,b_0)=b_1\)可以转换为：

\[ lcm(x,b_0)=b_1 \\ gcd(x,b_0)*lcm(x,b_0)=xb_0 \\ gcd(x,b_0)=\frac{xb_0}{b_1} \\ gcd(\frac{b_1}{b_0},\frac{b_1}{x})=1 \]

可以看出，\(x\)为\(b_1\)的一个约数，\(a_1\)是\(x\)的一个约束，根据这两个条件和两个\(gcd\)条件，进行枚举即可。

代码

// CH3201.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a0, a1, b0, b1;
int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        int ans = 0;
        scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
        int p = b1 / b0, q = a0 / a1;
        for (int x = 1; x * x <= b1; x++)
            if (b1 % x == 0)
            {
                if (x % a1 == 0 && gcd(p, b1 / x) == 1 && gcd(q, x / a1) == 1)
                    ans++;
                int y = b1 / x;
                if (x == y)
                    continue;
                if (y % a1 == 0 && gcd(p, b1 / y) == 1 && gcd(q, y / a1) == 1)
                    ans++;
            }
        printf("%d\n", ans);
    }
    return 0;
}