#### Problem’s Main Idea

• $n$个询问，每个询问给定 $a_0, a_1, b_0, b_1$, 求有多少个 $x$满足 $\gcd(a_0,x)=a_1,\ \mathrm{lcm}(b_0,x)=b_1$。
• 数据范围：$n \le 2e3,1 \le a_0,a_1,b_0,b_1 \le 2e9$

#### Solution

$\gcd(a_0,x)=a_1$

$\Rightarrow \ \begin{cases} x=k_1 \times a_1 \\ a_0=k_2 \times a_1 \ \end{cases}$

$\Rightarrow \ \gcd(k_1,k_2)=1$

$\Rightarrow \ \begin{cases} k_1=p \times K\\ k_2=q \times K \end{cases}$

$\Rightarrow \ \begin{cases} x=p \times K \times a_1\\ a_0=q \times K \times a_1 \end{cases}$

$\Rightarrow \ \gcd(x,a_0)=K \times a_1 \not= a_1$

$\forall a,b \in N_{+},\ \gcd(a,b)=k$
$\Rightarrow \ \gcd(a/k,b/k)=1$

$\mathrm{lcm}(b_0, x)=b_1$
$\Rightarrow \ b_0 \times x / \gcd(b_0,x) = b_1$
$\therefore \gcd(b_0,x)=b_0 \times x / \mathrm{lcm}(b_0,x)=b_0 \times x / b_1$
$\Rightarrow \ \gcd(b_0/(b_0 \times x / b_1),x/(b_0 \times x / b_1)) = 1$
$\Rightarrow \ \gcd(b_1/x,b_1/b_0) = 1$

$\begin{cases} \gcd(x/a_1,a_0/a_1)=1 \\ \gcd(b_1/x,b_1/b_0)=1 \end{cases}$

#### Code

//Coded by Dy.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
#define pc(x) putchar(x)
typedef long long ll;
#define int ll
int sc()
{
int xx = 0, ff = 1; char cch = gc;
while(!isdigit(cch) && cch != EOF)
{
if(cch == '-') ff = -1; cch = gc;
}
while(isdigit(cch))
{
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
void out(int x)
{
if(x < 0) pc('-'), x = -x;
if(x >= 10) out(x / 10);
pc(x % 10 + '0');
}
#undef int
ll n, a0, a1, b0, b1, ans;
ll gcd(ll x, ll y)
{
if(y == 0) return x;
return gcd(y, x % y);
}
int main()
{
n = sc();
while(n--)
{
ans = 0;
a0 = sc(), a1 = sc(), b0 = sc(), b1 = sc();
for(ll i = 1; i * i <= b1; ++i)
{
if(b1 % i == 0)
{
if(i % a1 == 0 && gcd(b1 / b0, b1 / i) == 1 && gcd(i / a1, a0 / a1) == 1) ++ans;
if(b1 / i != i)
{
ll tem = b1 / i;
if(tem % a1 == 0 && gcd(b1 / b0, b1 / tem) == 1 && gcd(tem / a1, a0 / a1) == 1) ++ans;
}
}
}
out(ans), pc('\n');
}
return 0;
}


$$2019 \ CSP-S \ Rp++$$

#### DyRisingSunlight

I am Dy. An OIer from SD Province.