1626：【例 2】Hankson 的趣味题

题目描述

Hanks 博士是 BT（Bio-Tech，生物技术）领域的知名专家，他的儿子名叫 Hankson。现在，刚刚放学回家的 Hankson 正在思考一个有趣的问题。

今天在课堂上，老师讲解了如何求两个正整数 $c_1$ 和 $c_2$ 的最大公约数和最小公倍数。现在 Hankson 认为自己已经熟练地掌握了这些知识，他开始思考「求公约数」和「求公倍数」这类问题的一个逆问题，这个问题是这样的：已知正整数 $a_0, a_1, b_0, b_1$，设某未知正整数 $x$ 满足：

1. $x$ 和 $a_0$ 的最大公约数是 $a_1$；
2. $x$ 和 $b_0$ 的最小公倍数是 $b_1$。

Hankson 的「逆问题」就是求出满足条件的正整数 $x$。但稍加思索之后，他发现这样的 $x$ 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 $x$ 的个数。请你帮助他编程求解这个问题。

输入格式

第一行为一个正整数 $n$，表示有 $n$ 组输入数据。

接下来的 $n$ 行每行一组输入数据，为四个正整数 $a_0, a_1, b_0, b_1$，每两个整数之间用一个空格隔开。

输入数据保证 $a_0$ 能被 $a_1$ 整除，$b_1$ 能被 $b_0$ 整除。

输出格式

共 $n$ 行。每组输入数据的输出结果占一行，为一个整数。

对于每组数据：若不存在这样的 $x$，请输出 $0$；若存在这样的 $x$，请输出满足条件的 $x$ 的个数。

样例

样例输入 #1

2
41 1 96 288
95 1 37 1776

样例输出 #1

6
2

样例解释 #1

第一组数据：

• $a_0=41, a_1=1, b_0=96, b_1=288$
• 条件：
  1. $\gcd(x, 41) = 1$
  2. $\mathrm{lcm}(x, 96) = 288$
• 满足条件的 $x$ 有：$9, 18, 36, 72, 144, 288$，共 $6$ 个。

第二组数据：

• $a_0=95, a_1=1, b_0=37, b_1=1776$
• 条件：
  1. $\gcd(x, 95) = 1$
  2. $\mathrm{lcm}(x, 37) = 1776$
• 满足条件的 $x$ 有：$48, 1776$，共 $2$ 个。

数据范围

• 对于 $50\%$ 的数据，保证有 $a_0, a_1, b_0, b_1 \le 10^4$，且 $n \le 100$。
• 对于 $100\%$ 的数据，保证有 $1 \le a_0, a_1, b_0, b_1 \le 2 \times 10^9$，且 $n \le 2000$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题需要根据条件推导 $x$ 的性质。设 $\gcd(x, a_0) = a_1$，则 $x$ 必须是 $a_1$ 的倍数，且 $x / a_1$ 与 $a_0 / a_1$ 互质。另外，$\mathrm{lcm}(x, b_0) = b_1$，则 $x$ 必须是 $b_1$ 的因数，且 $b_1 / x$ 与 $b_1 / b_0$ 互质？实际上，由 $\mathrm{lcm}(x, b_0) = b_1$，可得 $x \mid b_1$，且 $\gcd(x, b_0) = \frac{x \cdot b_0}{b_1}$？更直接的方法：对于每个质因子 $p$，考虑它在 $a_0, a_1, b_0, b_1, x$ 中的指数。设 $x$ 中 $p$ 的指数为 $t$，$a_0$ 中为 $\alpha_0$，$a_1$ 中为 $\alpha_1$，$b_0$ 中为 $\beta_0$，$b_1$ 中为 $\beta_1$。则条件转化为：

1. $\min(t, \alpha_0) = \alpha_1$
2. $\max(t, \beta_0) = \beta_1$

对每个质因子 $p$，我们可以根据 $\alpha_0, \alpha_1, \beta_0, \beta_1$ 确定 $t$ 的取值范围（可能无解，可能唯一，可能两个值）。然后将所有质因子的取值范围乘起来（乘法原理）得到 $x$ 的个数。

具体地，对于每个质因子 $p$，分情况讨论：

• 如果 $\alpha_0 = \alpha_1$，则条件1要求 $t \ge \alpha_1$；如果 $\alpha_0 > \alpha_1$，则条件1要求 $t = \alpha_1$。
• 如果 $\beta_0 = \beta_1$，则条件2要求 $t \le \beta_1$；如果 $\beta_0 < \beta_1$，则条件2要求 $t = \beta_1$。 综合两者，可以确定 $t$ 的取值个数（$0,1,2$ 个）。如果出现矛盾（如要求 $t$ 同时等于两个不同的值），则无解。

由于 $a_0, a_1, b_0, b_1 \le 2\times 10^9$，质因子个数有限，我们可以对 $b_1$ 分解质因数（因为 $x$ 是 $b_1$ 的因数），然后对每个质因子讨论。注意还要考虑 $b_1$ 的质因子可能不在 $a_0$ 中，此时 $\alpha_0 = \alpha_1 = 0$，条件1变为 $\min(t,0)=0$，即 $t \ge 0$（恒成立），条件2同上。另外，$x$ 还可能包含 $b_1$ 中没有的质因子吗？因为 $x \mid b_1$，所以 $x$ 的质因子只能是 $b_1$ 的质因子，且指数不超过 $\beta_1$。所以只需对 $b_1$ 的每个质因子讨论即可。

算法步骤：

1. 对每组数据，分解 $b_1$ 的质因数（因为 $n \le 2000$，$b_1 \le 2\times 10^9$，可以用试除法分解，注意优化到 $\sqrt{b_1}$）。
2. 对于每个质因子 $p$，求出它在 $a_0, a_1, b_0, b_1$ 中的指数（用除法反复除）。
3. 根据上述规则确定 $t$ 的取值个数。
4. 将所有质因子的取值个数相乘，得到答案。

注意：如果 $b_1$ 是大质数，试除法需要枚举到 $\sqrt{b_1}$，但 $b_1 \le 2\times 10^9$，$\sqrt{b_1} \le 44721$，可以接受。但 $n=2000$，最坏情况 $2000 \times 44721 \approx 10^8$ 次除法，可能超时。可以预处理所有 $\sqrt{2\times 10^9}$ 以内的质数（约 $44721$ 以内的质数，约 $5000$ 个），然后用这些质数去分解，可以加速。