[NOIP2009-提高] Hankson的趣味题

题目描述

Hankson 在思考 gcd/lcm 的"逆问题"：给定正整数 $a_0,a_1,b_0,b_1$ （保证 $a_1\mid a_0$ ， $b_0\mid b_1$ ），统计满足 $\gcd(x,a_0)=a_1$ 且 $\operatorname{lcm}(x,b_0)=b_1$ 的正整数 $x$ 的个数；不存在则答案为 $0$ 。输入第一行为正整数 $n$ ，接下来 $n$ 行每行四个正整数 $a_0,a_1,b_0,b_1$ （ $1\leqslant a_0,a_1,b_0,b_1\leqslant 2\times 10^9$ ， $n\leqslant 2000$ ）；输出共 $n$ 行，每行即满足条件的 $x$ 的个数（不存在输出 $0$ ）。例如输入三行 2、41 1 96 288、95 1 37 1776，输出两行 6、2。

思路

由条件一知 $a_1\mid x$ ，由条件二知 $x\mid b_1$ ，所以合法的 $x$ 只能是 $b_1$ 的约数。对 $b_1$ 做 $O(\sqrt{b_1})$ 试除枚举每个约数 $d$ ，依次验证 $d\bmod a_1=0$ 、 $\gcd(d,a_0)=a_1$ 、以及乘积等式 $d\cdot b_0=b_1\cdot\gcd(d,b_0)$ （等价于 $\operatorname{lcm}(d,b_0)=b_1$ ），全部通过就计数。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 08:25
# update_at: 2026-10-02 08:25

from itertools import count
from math import gcd, isqrt


def divisors_of(b1: int) -> list[int]:
    """返回 b1 的全部约数：试除出 <=sqrt(b1) 的 d，再配对 b1//d。

    b1 ≤ 2×10⁹，√b1 ≈ 44722，逐个试除即可；同一 d 与 b1//d 去重靠 i*i <= b1
    时只取一个。
    """
    divs = [d for d in range(1, isqrt(b1) + 1) if b1 % d == 0]
    divs += [b1 // d for d in reversed(divs) if b1 // d != d]
    return divs


def count_x(a0: int, a1: int, b0: int, b1: int) -> int:
    """统计满足 gcd(x,a0)=a1 且 lcm(x,b0)=b1 的正整数 x 的个数。"""
    total = sum(
        1
        for d in divisors_of(b1)
        if d % a1 == 0                                  # gcd(x,a0) 必是 x 的约数
        and gcd(d, a0) == a1
        and d * b0 == b1 * gcd(d, b0)                   # lcm(x,b0)·gcd(x,b0)=x·b0
    )
    return total


def solve() -> None:
    data = iter(map(int, open(0).read().split()))
    n = next(data)
    for _ in range(n):
        a0, a1, b0, b1 = (next(data) for _ in range(4))
        print(count_x(a0, a1, b0, b1))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
53
54
55
56
57/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:26
 * update_at: 2026-10-06 14:26
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 5000; // 约数最多 1500 个左右，开 5000 足够

ll a0, a1, b0, b1;     // 每组输入的四个数
ll divs[MAXN];         // divs[i] 存 b1 的第 i 个约数（试除生成）
int cnt;               // b1 的约数个数

// 求最大公约数
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// 用试除把 b1 的全部约数存进 divs[]：d <= sqrt(b1) 时同时拿到 d 和 b1/d
void get_divisors(ll x) {
    cnt = 0;
    for (ll d = 1; d * d <= x; ++d) {
        if (x % d == 0) {
            divs[cnt++] = d;
            if (d != x / d) divs[cnt++] = x / d;
        }
    }
}

// 判断候选 d 是否满足 gcd(d,a0)=a1 且 lcm(d,b0)=b1
bool check(ll d) {
    if (d % a1 != 0) return false;      // a1 | d 是必要条件，先廉价筛掉
    if (gcd(d, a0) != a1) return false; // 条件一
    // lcm(d,b0) = d*b0/gcd(d,b0)，避免直接除，改判乘积等式 d*b0 = b1*gcd(d,b0)
    if (d * b0 != b1 * gcd(d, b0)) return false;
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        scanf("%lld %lld %lld %lld", &a0, &a1, &b0, &b1);
        get_divisors(b1); // x 必须既是 a1 的倍数又整除 b1，所以只需枚举 b1 的约数
        int ans = 0;
        for (int i = 0; i < cnt; ++i)
            if (check(divs[i])) ++ans;
        printf("%d\n", ans);
    }
    return 0;
}