题解：Hankson 的逆问题（数论 + 质因数分解）

一、解题核心思路

本题是 GCD/LCM 逆问题，核心是通过已知条件推导未知整数 x 的约束，最终通过质因数分解统计合法 x 的个数。关键在于将 x 的约束转化为质因数指数的约束，利用数论性质简化问题：

二、关键数论性质与约束推导

已知 x 需满足：

1. gcd(x, a₀) = a₁
2. lcm(x, b₀) = b₁

核心推导：

1. 约束 1 分析：

   • x 必须是 a₁ 的倍数（a₁ | x），否则 gcd(x, a₀) 不可能为 a₁。
   • 设 a' = a₀ / a₁，则 x/a₁ 与 a' 必须互质（gcd(x/a₁, a') = 1），否则 gcd(x, a₀) 会大于 a₁。

2. 约束 2 分析：

   • x 必须是 b₁ 的约数（x | b₁），否则 lcm(x, b₀) 不可能为 b₁。
   • 设 m = b₁ / a₁，若 b₁ 不能被 a₁ 整除（b₁ % a₁ ≠ 0），则 x 不存在（因 x 需同时是 a₁ 的倍数和 b₁ 的约数）。

3. 质因数指数约束： 对任意质数 p，设 v_p(n) 表示 n 的质因数分解中 p 的指数。则：

   • 约束 1 转化为：min(v_p(x), v_p(a₀)) = v_p(a₁)
   • 约束 2 转化为：max(v_p(x), v_p(b₀)) = v_p(b₁)

三、具体解题步骤

步骤 1：初步无解判断

• 若 b₁ % a₁ ≠ 0 → 无解（x 需同时是 a₁ 的倍数和 b₁ 的约数）。
• 计算 a' = a₀ / a₁、m = b₁ / a₁（x = a₁ * k，k 需整除 m）。

步骤 2：质因数分解

对以下数字进行质因数分解（试除法，适用于 ≤ 2×10⁹ 的数字）：

• m：x = a₁*k 中 k 的质因数来源。
• a'：判断 k 需排除的质因数。
• a₁、b₀、b₁：获取各质因数的指数，用于约束判断。

步骤 3：逐质因数约束校验与计数

对 m 的每个质因数 p，结合约束推导 v_p(x) 的合法取值数量：

1. 获取指数：
   • v_a1 = v_p(a₁)（a₁ 中 p 的指数）
   • v_b0 = v_p(b₀)（b₀ 中 p 的指数）
   • v_b1 = v_p(b₁)（b₁ 中 p 的指数）
2. 分情况讨论：
   • 若 p 整除 a'（k 不能含 p）：
     • v_p(x) = v_a1，需满足 max(v_a1, v_b0) = v_b1 → 不满足则无解。
   • 若 p 不整除 a'（k 可含 p）：
     • 若 v_b0 < v_b1 → v_p(x) 必须为 v_b1（仅 1 种选择）。
     • 若 v_b0 == v_b1 → v_p(x) 可在 [v_a1, v_b1] 中取值（共 v_b1 - v_a1 + 1 种选择）。

步骤 4：补充校验 a₁ 的额外质因数

a₁ 可能含不在 m 中的质因数 p（k 不含 p，故 v_p(x) = v_p(a₁)），需校验 max(v_p(a₁), v_p(b₀)) = v_p(b₁) → 不满足则无解。

步骤 5：统计合法 x 的个数

所有质因数的合法取值数量的乘积，即为答案（质因数指数选择独立）。

四、完整代码实现

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

// 质因数分解：返回 n 的质因数及其指数（n ≥ 1）
map<int, int> factorize(int n) {
    map<int, int> res;
    if (n == 1) return res;
    for (int i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            res[i]++;
            n /= i;
        }
    }
    if (n > 1) res[n]++;
    return res;
}

// 计算 n 中质因数 p 的指数（n ≥ 1，p ≥ 2）
int get_exponent(int n, int p) {
    int cnt = 0;
    while (n % p == 0 && n > 0) {
        cnt++;
        n /= p;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        int a0, a1, b0, b1;
        cin >> a0 >> a1 >> b0 >> b1;
        
        // 初步无解判断：b1 必须是 a1 的倍数
        if (b1 % a1 != 0) {
            cout << 0 << '\n';
            continue;
        }
        
        int a_prime = a0 / a1;
        int m_val = b1 / a1;
        
        // 质因数分解
        auto m_factors = factorize(m_val);
        auto a_prime_factors = factorize(a_prime);
        auto a1_factors = factorize(a1);
        
        long long ans = 1;
        
        // 处理 m 的所有质因数
        for (auto &[p, exp_m] : m_factors) {
            int v_a1 = get_exponent(a1, p);
            int v_b0 = get_exponent(b0, p);
            int v_b1 = get_exponent(b1, p);
            
            // 判断 p 是否整除 a'
            bool p_divides_a_prime = (a_prime_factors.count(p) > 0);
            
            if (p_divides_a_prime) {
                // 约束：v_p(x) = v_a1，需满足 max(v_a1, v_b0) = v_b1
                if (max(v_a1, v_b0) != v_b1) {
                    ans = 0;
                    break;
                }
            } else {
                // 约束：v_p(x) ∈ [v_a1, v_b1]
                if (v_a1 > v_b1) {
                    ans = 0;
                    break;
                }
                // 根据 v_b0 与 v_b1 的关系计算可选数
                if (v_b0 < v_b1) {
                    // 必须取 v_b1，仅 1 种选择
                    continue;
                } else {
                    // v_b0 == v_b1，可选数为 v_b1 - v_a1 + 1
                    ans *= (v_b1 - v_a1 + 1);
                }
            }
        }
        
        // 处理 a1 的质因数中不在 m 中的部分
        if (ans != 0) {
            for (auto &[p, exp_a1] : a1_factors) {
                if (m_factors.count(p) == 0) {
                    // 约束：v_p(x) = exp_a1，需满足 max(exp_a1, v_b0) = v_b1
                    int v_b0 = get_exponent(b0, p);
                    int v_b1 = get_exponent(b1, p);
                    if (max(exp_a1, v_b0) != v_b1) {
                        ans = 0;
                        break;
                    }
                }
            }
        }
        
        cout << ans << '\n';
    }
    return 0;
}

五、代码解释

1. 质因数分解函数：factorize 用试除法分解数字，返回质因数及其指数；get_exponent 快速获取单个质因数的指数。
2. 初步无解判断：快速排除 b1 不能被 a1 整除的情况，减少无效计算。
3. 质因数约束处理：逐质因数校验约束，统计合法取值数量，利用乘法原理累计答案。
4. 补充校验：处理 a1 中未出现在 m 中的质因数，确保所有约束都被满足。

六、复杂度分析

• 时间复杂度：每组数据的质因数分解时间为 O(√n)（n ≤ 2×10⁹，√n ≤ 4.5×10⁴），n ≤ 2000 组数据，总时间可接受。
• 空间复杂度：存储质因数的映射表，空间开销极小（质因数个数不超过 log2(2×10⁹) ≈ 31）。

该代码通过数论推导简化约束，利用质因数分解精准统计合法解，高效解决了题目中的逆问题。