「一本通 6.4 例 2」同余方程

题目描述

求同余方程 $ax \equiv 1 \pmod b$ 的最小正整数解。输入一行两个正整数 $a, b$ （ $2 \le a, b \le 2 \times 10^9$ ），保证有解；输出最小正整数解 $x_0$ 。样例输入 3 10，输出 7。

思路

$ax \equiv 1 \pmod b$ 等价于 $ax + by = 1$ ，因保证有解故 $\gcd(a, b) = 1$ 。用扩展欧几里得求出一组特解 $x$ ，通解为 $x + kb$ ，把 $x$ 取模调整到 $[1, 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
26
27
28
29
30
31#!/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:08
# update_at: 2026-09-30 23:08

import sys


def exgcd(a: int, b: int) -> tuple[int, int, int]:
    """扩展欧几里得算法：返回 (g, x, y) 使得 a*x + b*y = g = gcd(a, b)。"""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = exgcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def solve() -> None:
    data = sys.stdin.read().split()
    if not data:
        return
    a, b = map(int, data)
    _, x, _ = exgcd(a, b)
    # 调整为最小正整数解
    ans = (x % b + b) % b
    print(ans if ans != 0 else 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/**
 * 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 01:24
 * update_at: 2026-10-06 01:24
 */
#include <iostream>

typedef long long ll;

// 扩展欧几里得：求出 a*x + b*y = gcd(a, b) 的一组特解 x, y
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, x, y);
    ll nx = y;
    ll ny = x - (a / b) * y;
    x = nx;
    y = ny;
    return g;
}

int main() {
    ll a, b;
    std::cin >> a >> b;

    ll x, y;
    exgcd(a, b, x, y);

    // 通解为 x + k*b，把特解调整到 [1, b] 内的最小正整数
    ll ans = (x % b + b) % b;
    if (ans == 0) {
        ans = b;
    }
    std::cout << ans << std::endl;
    return 0;
}

「一本通 6.4 例 2」同余方程

目录

题目描述

思路

参考代码