题意

给出两个正整数 $x_0, y_0$。
要求统计有多少组正整数有序对 (P,Q) 满足：

• $\gcd(P,Q) = x_0$
• $\operatorname{lcm}(P,Q) = y_0$

思路

先看一个可以直接验证想法的朴素解：

把题目改写成：

• $P = x_0 \cdot a$
• $Q = x_0 \cdot b$

那么只要枚举 $n = y_0 / x_0$ 的所有因子对 (a,b)，检查它们是否互质，就能数出答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll x0, yv;

ll gcd_ll(ll a, ll b) {
    while (b != 0) {
        ll t = a % b;
        a = b;
        b = t;
    }
    return a;
}

void solve() {
    if (yv % x0 != 0) {
        cout << 0 << '\n';
        return;
    }

    ll n = yv / x0;
    ll ans = 0;

    for (ll a = 1; a * a <= n; a++) {
        if (n % a != 0) {
            continue;
        }
        ll b = n / a;
        if (gcd_ll(a, b) == 1) {
            if (a == b) {
                ans += 1;
            } else {
                ans += 2;
            }
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> x0 >> yv;
    solve();

    return 0;
}

这个想法已经很接近正解了，关键只差最后一步：

既然要求 $\gcd(a,b)=1$，那 $n = y_0 / x_0$ 的每个质因子幂次块就不能同时分给 a 和 b。

例如若：

$n = 2^2 \times 5$

那么方案只会是下面四种：

表格里每个“质因子块”都只有两种去向：给左边或给右边。
所以如果 n 有 k 个不同质因子，总方案数就是：

2^k

于是正式做法就很简单：

1. 先判断 y0 是否能被 x0 整除；
2. 令 $n = y_0 / x_0$；
3. 对 n 做试除分解；
4. 每发现一个新的不同质因子，就让答案乘 2。

Python 知识

• Python 整数不会溢出，可以直接计算质因子块数量对应的 1 << k。
• while quotient % prime == 0 一次除尽同一质因子，只统计不同质因子个数。
• 位移 1 << distinct_primes 就是 $2^k$，准确表达每个质因子块的二选一。
• 先检查整除关系，避免对不可能的输入继续分解。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：Python 任意精度整数。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/map_reduce_filter.md：把独立选择归约成乘积的思路。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19import sys


gcd_value, lcm_value = map(int, sys.stdin.buffer.read().split())
if lcm_value % gcd_value:
    print(0)
else:
    quotient = lcm_value // gcd_value
    distinct_primes = 0
    prime = 2
    while prime * prime <= quotient:
        if quotient % prime == 0:
            distinct_primes += 1
            while quotient % prime == 0:
                quotient //= prime
        prime += 1
    if quotient > 1:
        distinct_primes += 1
    print(1 << distinct_primes)

复杂度

设 $n = y_0 / x_0$，时间复杂度是 $O(\sqrt{n})$，空间复杂度是 $O(1)$。

总结

这题表面在数 (P,Q)，本质在数 y0/x0 的不同质因子块如何分给左右两边。

把 gcd 和 lcm 先拆开之后，问题会一下子变成很标准的数论计数题。