「一本通 6.3 练习 3」Super GCD

形式化题目

给定两个正整数 $A$ 和 $B$ （ $0 < A, B \leqslant 10^{10000}$ ），求它们的最大公约数 $\gcd(A, B)$ 。

输入两行，每行一个十进制大整数；输出一行，即 $\gcd(A, B)$ 。

暴力解法

思路

最容易想到的是标准的欧几里得算法：

\gcd(A, B) = \gcd(B, A \bmod B)

对普通大小的整数它非常快。但本题 $A, B$ 最多有约 $10001$ 位十进制数字，一次取模就是一次完整的大数除法：C++ 里需要手写高精度除法，Python 里虽然 math.gcd 帮你封装好了，但除法本身在这类量级上代价依然很高。瓶颈清晰可见——取模 = 大数除法。

代码

复杂度

单次取模 $O(n^2)$ （ $n$ 为位数），总复杂度 $O(n^2 \log \max(A,B))$ 量级，且实现繁重。

瓶颈

欧几里得算法的核心运算"取模"无法回避大数除法。要消除它，就必须找一个只用移位、比较、减法的 gcd 算法。

正解

思路

Stein 二进制 GCD（又称"移位减法 GCD"）正是为这个瓶颈设计的。它基于三条 gcd 性质：

$\gcd(2a, 2b) = 2\cdot\gcd(a, b)$ ——公因子 2 可以直接提出；
$\gcd(2a, b) = \gcd(a, b)$ （ $b$ 为奇数时）——只有一个数是偶数时，因子 2 不贡献 gcd，直接去掉；
$\gcd(a, b) = \gcd(a, b - a)$ （ $a, b$ 均为奇数时）——两个奇数之差是偶数。

在二进制下，"除以 2"就是右移一位，代价远低于一次除法。算法流程如下：

flowchart TD
    A[输入 a, b] --> B["k = min(v2(a), v2(b))<br/>一次性提出公因子 2"]
    B --> C["a 去掉全部尾零<br/>此后 a 一直是奇数"]
    C --> D{b = 0 ?}
    D -- 是 --> E["输出 a << k"]
    D -- 否 --> F["b 去掉全部尾零"]
    F --> G{a > b ?}
    G -- 是 --> H["交换 a, b"]
    G -- 否 --> I["b ← b - a"]
    H --> I
    I --> D

第一步统计 $v_2$ （2 的幂次）用位技巧 (x & -x).bit_length() - 1 一次完成；
循环中只给 $b$ 去尾零、 $a$ 保持奇数，这样每轮只做一次比较和一次减法；
关键在第 3 条性质：两个奇数相减必得偶数，所以 $b$ 减完之后下一轮至少还能再右移一位——这就是规模快速下降、总轮数维持在 $O(\log \max(A,B))$ 量级的原因。

用一个具体的二进制例子走一遍（求 $\gcd(48, 36)$ ， $k=2$ ）：

轮次	操作	a（二进制）	b（二进制）	说明
初始	提出 $2^2$ ，a 去尾零	`11`	`1001`	$48=2^2\cdot12$ ， $36=2^2\cdot9$
1	b 去尾零；b − a	`11`	`110`	`1001 − 11 = 110`（偶数）
2	b 去尾零	`11`	`11`	相等了
3	b − a = 0	`11`	`0`	循环结束
输出	a 左移 $k=2$ 位	—	—	$\gcd = 3 \times 4 = 12$ ✓

观察点：每次"减法 → 尾零 → 右移"的组合都在把 $b$ 的有效位数往下压； $a$ 从头到尾保持奇数，省掉一半工作量。

还有一个 Python 特有的坑：Python 3.11 起，int 与字符串互转默认有 4300 位的上限， $10^{10000}$ 级的输入会直接抛 ValueError。必须先执行 sys.set_int_max_str_digits(0) 解除限制，再读入大数。

代码

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-09-30 23:10
# update_at: 2026-09-30 23:10

import sys

sys.set_int_max_str_digits(0)   # 解除 $10^{10000}$ 级大数与字符串互转的默认 4300 位上限


def trailing_zeros(x: int) -> int:
    """取 x 二进制尾部 0 的个数，即 x 含因子 2 的幂次。"""
    return (x & -x).bit_length() - 1


def binary_gcd(a: int, b: int) -> int:
    """Stein 二进制 GCD：只用移位、减法和比较，避免对 $10^{10000}$ 级大数做除法取模。"""
    if a == 0:                      # 较小数为 0 时 gcd 就是另一个数
        return b
    if b == 0:
        return a

    shift = min(trailing_zeros(a), trailing_zeros(b))  # 公共因子 2 的个数

    a >>= trailing_zeros(a)         # 之后 a 一直是奇数
    while b:
        b >>= trailing_zeros(b)     # 去掉 b 的尾零：奇偶差异不贡献 gcd
        if a > b:
            a, b = b, a
        b -= a                      # 奇 - 奇 = 偶，下一轮还能整除 2，规模减半
    return a << shift               # 补回公共因子 2


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())  # 仅按位置顺序消费两个大整数字串
    a = int(next(data))                           # 第一个 $10^{10000}$ 级大数
    b = int(next(data))
    print(binary_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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185/**
 * 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 23:22
 * update_at: 2026-10-05 23:22
 */
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

// 手写高精度：以 10^9 为一位，低位在前。
// 本题 A,B 最多 10^10000，约 1112 个 10^9 进制位，开 1200 足够。
const int BASE = 1000000000;
const int MAXL = 1200;

struct Big {
    int len;        // 有效位数（以 10^9 为一位，至少为 1）
    int a[MAXL];    // a[0] 是最低 9 位，依次向高位存
};

Big ga; // 第一个大数
Big gb; // 第二个大数

// 去掉高位多余的 0，零统一表示为 len = 1 且 a[0] = 0
void big_trim(Big &x) {
    while (x.len > 1 && x.a[x.len - 1] == 0) {
        x.len--;
    }
}

// 读入一个十进制大整数串，从低位开始每 9 个数字打包成一位
void big_read(Big &x) {
    string s;
    cin >> s;
    for (int i = 0; i < MAXL; i++) {
        x.a[i] = 0;
    }
    x.len = 0;
    int n = s.size();
    for (int end = n; end > 0; end -= 9) {
        int start = end - 9;
        if (start < 0) {
            start = 0;
        }
        int value = 0;
        for (int i = start; i < end; i++) {
            value = value * 10 + (s[i] - '0');
        }
        x.a[x.len] = value;
        x.len++;
    }
    big_trim(x);
}

bool big_is_zero(const Big &x) {
    return x.len == 1 && x.a[0] == 0;
}

// 十进制大数看最低位即可判断奇偶
bool big_is_even(const Big &x) {
    return x.a[0] % 2 == 0;
}

// x /= 2，从高位向低位处理，余数借给下一位
void big_div2(Big &x) {
    int carry = 0;
    for (int i = x.len - 1; i >= 0; i--) {
        int cur = x.a[i] + carry * BASE;
        x.a[i] = cur / 2;
        carry = cur % 2;
    }
    big_trim(x);
}

// x *= 2，从低位向高位进位
void big_mul2(Big &x) {
    int carry = 0;
    for (int i = 0; i < x.len; i++) {
        int cur = x.a[i] * 2 + carry;
        x.a[i] = cur % BASE;
        carry = cur / BASE;
    }
    if (carry > 0) {
        x.a[x.len] = carry;
        x.len++;
    }
}

// 返回 -1 / 0 / 1 表示 x < y / x == y / x > y
int big_cmp(const Big &x, const Big &y) {
    if (x.len != y.len) {
        return x.len < y.len ? -1 : 1;
    }
    for (int i = x.len - 1; i >= 0; i--) {
        if (x.a[i] != y.a[i]) {
            return x.a[i] < y.a[i] ? -1 : 1;
        }
    }
    return 0;
}

// x -= y，调用前保证 x >= y
void big_sub(Big &x, const Big &y) {
    int borrow = 0;
    for (int i = 0; i < x.len; i++) {
        int yv = (i < y.len) ? y.a[i] : 0;
        int cur = x.a[i] - yv - borrow;
        if (cur < 0) {
            cur += BASE;
            borrow = 1;
        } else {
            borrow = 0;
        }
        x.a[i] = cur;
    }
    big_trim(x);
}

void big_swap(Big &x, Big &y) {
    Big tmp = x;
    x = y;
    y = tmp;
}

// 高位直接输出，其余每位补足 9 位前导零
void big_print(const Big &x) {
    printf("%d", x.a[x.len - 1]);
    for (int i = x.len - 2; i >= 0; i--) {
        printf("%09d", x.a[i]);
    }
    printf("\n");
}

// Stein 二进制 GCD：只用去尾零（除 2）、比较和减法，避免高精度大数除法取模。
void solve() {
    big_read(ga);
    big_read(gb);
    if (big_is_zero(ga)) {
        big_print(gb);
        return;
    }
    if (big_is_zero(gb)) {
        big_print(ga);
        return;
    }

    int shift = 0; // 两数公共因子 2 的个数，最后再补回
    while (big_is_even(ga) && big_is_even(gb)) {
        big_div2(ga);
        big_div2(gb);
        shift++;
    }
    while (big_is_even(ga)) {
        big_div2(ga);
    }
    while (big_is_even(gb)) {
        big_div2(gb);
    }

    // 此后 ga 恒为奇数；每轮把 gb 去尾零到奇数，再用大减小
    while (!big_is_zero(gb)) {
        while (big_is_even(gb)) {
            big_div2(gb);
        }
        if (big_cmp(ga, gb) > 0) {
            big_swap(ga, gb);
        }
        big_sub(gb, ga);
    }

    while (shift > 0) {
        big_mul2(ga);
        shift--;
    }
    big_print(ga);
}

int main() {
    solve();
    return 0;
}

复杂度

时间：每轮的尾零统计、比较、减法都是 $O(n)$ （ $n$ 为当前位数），总轮数 $O(\log \max(A,B))$ 量级，合计 $O(n \log \max(A,B))$ 。对 $n \approx 33000$ 个二进制位（ $10^{10000}$ ）大约是百万级位操作，实测最大测例仅 0.05 s。
空间： $O(n)$ ，存放两个大整数。

总结

本题唯一难点是 $10^{10000}$ 量级的大数 gcd：欧几里得算法的取模意味着大数除法，成为瓶颈。
Stein 二进制 GCD 用"提出公因子 2 + 去尾零 + 奇数相减"三条性质，把除法完全替换成移位、比较、减法，复杂度 $O(n \log \max(A,B))$ 。
Python 实现要点：(x & -x).bit_length() - 1 求尾零个数；sys.set_int_max_str_digits(0) 解除大数读入上限。