「一本通 6.3 例 2」Hankson 的趣味题

题目描述

给定正整数 $a_0,a_1,b_0,b_1$ ，求满足

\gcd(x,a_0)=a_1,\qquad \operatorname{lcm}(x,b_0)=b_1

的正整数 $x$ 的个数。其中 $1 \leqslant a_0,a_1,b_0,b_1 \leqslant 2\times 10^9$ ， $n \leqslant 2000$ 组询问；输入保证 $a_1 \mid a_0$ 且 $b_0 \mid b_1$ 。

思路

由 $\operatorname{lcm}(x,b_0)=b_1$ 可知 $x$ 必为 $b_1$ 的约数，因此只需枚举 $b_1$ 的所有约数（2e9 以内最多一千多个），再逐个验证 $\gcd(x,a_0)=a_1$ 与 $\operatorname{lcm}(x,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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61#!/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-09-30 22:56
# update_at: 2026-09-30 22:56

import sys
from math import gcd, isqrt, lcm

LIMIT = isqrt(2 * 10**9) + 1  # b1 的上界开平方，试除分解质因数只需试到这里


def prime_sieve(limit: int) -> list[int]:
    """筛出 limit 以内的全部素数：试除分解质因数时按素数表逐个试，跳过合数。"""
    is_prime = bytearray([1]) * limit
    is_prime[0:2] = b"\x00\x00"
    for p in range(2, isqrt(limit - 1) + 1):
        if is_prime[p]:
            is_prime[p * p :: p] = bytearray(len(is_prime[p * p :: p]))
    return [p for p in range(limit) if is_prime[p]]


PRIMES = prime_sieve(LIMIT)


def divisors(n: int) -> list[int]:
    """列出 n 的全部正因数：先试除分解，再让每个素因子的幂次乘进已有因数表。"""
    divs = [1]
    for p in PRIMES:
        if p * p > n:  # 已经试到 √n，剩余部分必定是 1 或单个素因子
            break
        if n % p:
            continue
        powers = [1]
        while n % p == 0:
            n //= p
            powers.append(powers[-1] * p)  # 该素因子的 0,1,...,k 次幂
        divs = [d * k for d in divs for k in powers]
    if n > 1:  # 剩下的大素因子，每个已有因数都可以选择乘或不乘它
        divs += [d * n for d in divs]
    return divs


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    n = next(data)

    for _ in range(n):
        a0, a1, b0, b1 = next(data), next(data), next(data), next(data)

        # lcm(x, b0) = b1 推出 x | b1，枚举范围由 [1, b1] 缩到 b1 的因数表（至多千余个）
        valid = sum(gcd(x, a0) == a1 and lcm(x, b0) == b1 for x in divisors(b1))
        out.append(str(valid))

    print("\n".join(out))


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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88/**
 * 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-09-30 23:06
 * update_at: 2026-10-06 01:25
 */
#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;

typedef long long ll;

const int MAXP = 50000;       // 筛到 44722 足够覆盖 sqrt(2e9)
int primes[MAXP];             // 素数表
bool is_composite[MAXP];      // 筛法标记
int prime_cnt;                // 素数个数
ll divisors[2000];            // b1 的约数表（2e9 内约数最多约 1536 个）
int div_cnt;                  // 当前约数个数

// 预处理 [2, MAXP) 范围内的素数表（埃氏筛）
void init_primes() {
    for (int i = 2; i < MAXP; ++i) {
        if (!is_composite[i]) primes[++prime_cnt] = i;
        for (int j = 1; j <= prime_cnt && (ll)i * primes[j] < MAXP; ++j) {
            is_composite[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

// 分解 n 的素因子，并通过笛卡尔积扩展出全部约数存入 divisors[]
void build_divisors(ll n) {
    div_cnt = 1;
    divisors[1] = 1;
    for (int i = 1; i <= prime_cnt && (ll)primes[i] * primes[i] <= n; ++i) {
        if (n % primes[i] != 0) continue;
        int e = 0;
        ll p = primes[i];
        while (n % p == 0) {
            n /= p;
            ++e;
        }
        // 把 p^0..p^e 乘进已有约数
        int old_cnt = div_cnt;
        ll pe = 1;
        for (int k = 1; k <= e; ++k) {
            pe *= p;
            for (int j = 1; j <= old_cnt; ++j) {
                divisors[++div_cnt] = divisors[j] * pe;
            }
        }
    }
    // 剩余部分为大于 sqrt(原n) 的素因子，指数为 1
    if (n > 1) {
        int old_cnt = div_cnt;
        for (int j = 1; j <= old_cnt; ++j) {
            divisors[++div_cnt] = divisors[j] * n;
        }
    }
}

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

    init_primes();

    int n;
    cin >> n;
    while (n--) {
        ll a0, a1, b0, b1;
        cin >> a0 >> a1 >> b0 >> b1;

        build_divisors(b1);

        int ans = 0;
        for (int i = 1; i <= div_cnt; ++i) {
            ll x = divisors[i];
            if (gcd(x, a0) == a1 && x / gcd(x, b0) * b0 == b1) {
                ++ans;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

「一本通 6.3 例 2」Hankson 的趣味题

目录

题目描述

思路

参考代码