求最大公约数问题

题目描述

给定两个正整数 $a, b$ （ $1 \leqslant a, b < 10^9$ ），求它们的最大公约数。一行读入两个正整数，输出一个正整数即为答案。

样例输入：6 9，样例输出：3。

思路

用辗转相除法：循环把 $(a, b)$ 替换为 $(b, a \bmod b)$ ，公因数集合不变而 $b$ 严格减小； $b=0$ 时直接输出 $a$ 。复杂度 $O(\log \min(a, b))$ 。

参考代码

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#!/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-29 23:37
# update_at: 2026-09-29 23:41

import sys


def gcd(a: int, b: int) -> int:
    """返回 a 与 b 的最大公约数：反复把 (a, b) 换成 (b, a % b)，b 归零时 a 就是答案。"""
    while b:
        a, b = b, a % b  # 余数严格变小，所以循环次数是 O(log min(a, b))
    return a


def solve() -> None:
    """读入一行里的两个正整数，输出它们的最大公约数。"""
    a, b = map(int, sys.stdin.buffer.read().split())
    print(gcd(a, b))


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/**
 * 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-05 05:32
 * update_at: 2026-10-05 05:32
 */
#include <cstdio>

typedef long long ll;

// gcd：辗转相除，反复把 (a, b) 换成 (b, a % b)，b 归零时 a 就是答案
ll gcd(ll a, ll b) {
    while (b != 0) {
        ll r = a % b; // 余数严格变小，循环次数为 O(log min(a, b))
        a = b;
        b = r;
    }
    return a;
}

int main() {
    ll a, b;
    if (scanf("%lld %lld", &a, &b) != 2) return 0;
    printf("%lld\n", gcd(a, b));
    return 0;
}

求最大公约数问题

目录

题目描述

思路

参考代码