[NOIP2001-普及]最大公约数和最小公倍数问题

题目描述

给定正整数 $x_0,y_0$ ，求有序正整数对 $(P,Q)$ 的个数，满足 $\gcd(P,Q)=x_0$ 且 $\operatorname{lcm}(P,Q)=y_0$ 。

输入一行两个正整数 $x_0,y_0$ ；输出一行一个整数表示答案。

样例： $3\ 60$ 时答案为 $4$ 。

思路

若 $x_0 \nmid y_0$ 则答案为 $0$ 。否则令 $k=y_0/x_0$ ，问题等价于把 $k$ 拆成互质有序对 $ab=k$ ，每个质因子幂只能整段给 $a$ 或 $b$ ，方案数为 $2^{\omega(k)}$ 。

参考代码

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#!/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 04:16
# update_at: 2026-10-02 04:16

import sys


def distinct_primes(k: int) -> int:
    """k 的不同质因数个数 ω(k)：试除到 √k，除尽的因子只计一次。"""
    count = 0
    d = 2
    while d * d <= k:
        if k % d == 0:
            count += 1
            while k % d == 0:  # 把 d 的整段幂次除尽，剩下的部分不再含 d
                k //= d
        d += 1
    return count + (k > 1)  # 剩余的 k 是一个大质数


def solve() -> None:
    x0, y0 = map(int, sys.stdin.buffer.read().split())

    # gcd(P,Q)=x0 且 lcm(P,Q)=y0 有解 ⇔ x0 | y0（gcd 必整除 lcm），否则答案为 0。
    if y0 % x0 != 0:
        print(0)
        return

    # 令 P=x0*a, Q=x0*b：gcd(a,b)=1 且 a*b=k（k=y0/x0）。
    # 互质要求把 k 的每个质因子整段幂次 p^e 全给 a 或全给 b，共 2^ω(k) 个有序对。
    k = y0 // x0
    print(1 << distinct_primes(k))


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/**
 * 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 12:16
 * update_at: 2026-10-06 12:16
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll x0_val, y0_val; // 题目输入：gcd 目标与 lcm 目标（避免 y0 与 math.h 的贝塞尔函数冲突）

// 返回 k 的不同质因子个数 ω(k)
int distinct_primes(ll k) {
    int cnt = 0;
    for (ll d = 2; d * d <= k; ++d) {
        if (k % d == 0) {
            ++cnt;          // 发现一个质因子，只计一次
            while (k % d == 0) k /= d; // 把 d 的整段幂除尽
        }
    }
    return cnt + (k > 1);   // 剩余部分若大于 1 是一个大质因子
}

int main() {
    scanf("%lld %lld", &x0_val, &y0_val);

    // gcd 必须整除 lcm，否则不存在这样的正整数对
    if (y0_val % x0_val != 0) {
        printf("0\n");
        return 0;
    }

    ll k = y0_val / x0_val;
    // 令 P=x0*a, Q=x0*b，则 ab=k 且 gcd(a,b)=1。
    // 互质要求 k 的每个质因子幂整段给 a 或 b，共 2^ω(k) 个有序对。
    printf("%d\n", 1 << distinct_primes(k));
    return 0;
}

[NOIP2001-普及]最大公约数和最小公倍数问题

目录

题目描述

思路

参考代码