形式化题目

给定正整数 $a, b$，求同余方程

的最小正整数解 $x_0$。数据保证方程有解，这等价于 $\gcd(a, b) = 1$；此时 $x_0$ 就是 $a$ 在模 $b$ 意义下的乘法逆元，所有解模 $b$ 同余，因此 $x_0$ 在 $1 \leqslant x_0 \leqslant b$ 内唯一。

样例：$a = 3,\ b = 10$ 时，$3 \times 7 = 21 \equiv 1 \pmod{10}$，而 $x = 1, \dots, 6$ 时 $3x \bmod 10$ 依次为 $3, 6, 9, 2, 5, 8$，均不为 $1$，故输出 $7$。

正解

思路

朴素做法。 从 $x = 1$ 开始逐个试，检查 $a \cdot x \bmod b = 1$，第一个命中者即答案。由"所有解模 $b$ 同余"知答案必在 $[1, b]$ 内，所以枚举上界是 $b$。40% 的数据 $b \leqslant 1000$ 时可行；但 $b$ 最大到 $2 \times 10^9$，$O(b)$ 的线性试探必然超时——瓶颈在于每次只排除一个候选，完全没有利用模运算的结构。

改写成不定方程。 同余式 $ax \equiv 1 \pmod b$ 的含义是"$ax$ 与 $1$ 相差 $b$ 的整数倍"，即

而 $ax + by = \gcd(a, b)$ 是扩展欧几里得算法的天然副产品，且 $\gcd(a, b) = 1$（方程有解 $\Rightarrow$ 互质），所以"求逆元"就被换成了"求这个不定方程的一组整数解"。

扩展欧几里得带出系数。 辗转相除的每一轮都维持线性组合

初始 $r_0 = a$（对应 $s_0 = 1$）、$r = b$（对应 $s = 0$）。设本轮商 $q = r_0 \mathbin{//} r$，则新余数 $r_0 - qr$ 的系数只需把旧系数同步减去 $q$ 倍：$(r_0, s_0) \leftarrow (r, s)$，$(r, s) \leftarrow (r_0 - qr,\ s_0 - qs)$。因为只关心 $x$ 方向，不变量可以直接写成同余形式 $r_0 \equiv s_0 \cdot a \pmod b$，省掉 $t_0$。循环在余数为 $0$ 时结束，此时 $r_0 = \gcd(a, b) = 1$，于是 $s_0 \cdot a \equiv 1 \pmod b$，$s_0$ 就是一个逆元；它可能是负数，对 $b$ 取模折回 $[0, b)$ 即最小正整数解（结果不可能是 $0$，否则 $s_0 a \equiv 0$，与 $r_0 = 1$ 矛盾）。

下表用样例 $(a, b) = (3, 10)$ 展示四变量 $(r_0, r, s_0, s)$ 的逐轮演化，最后一列检验不变量 $r_0 \equiv s_0 \cdot a \pmod{10}$：

观察重点：余数列 $10 \to 3 \to 1 \to 0$ 严格递减；最后一列（模 $10$ 后）依次为 $3, 0, 3, 1$，恰好每行都等于同行 $r_0$ 模 $10$（$3,\ 10 \equiv 0,\ 3,\ 1$），即不变量 $r_0 \equiv s_0 \cdot a \pmod{10}$ 逐步成立；结束时 $r_0 = 1$、$s_0 = -3$，答案 $(-3) \bmod 10 = 7$，与样例一致。

为什么不用费马小定理。 $x \equiv a^{b-2} \pmod b$ 只在 $b$ 为质数时给出逆元，本题 $b$ 可以是任意 $\geqslant 2$ 的整数，不能用；扩展欧几里得对任意互质的 $a, b$ 都成立。

代码

1
2
3
4
5
6
7
8
9
10
11
12/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); ll a,b; if(!(cin>>a>>b)) return 0; ll r0=a,r=b,s0=1,s=0; while(r){ ll q=r0/r; ll nr=r0-q*r; r0=r; r=nr; ll ns=s0-q*s; s0=s; s=ns; } cout << (s0%b+b)%b << '\n'; return 0; }

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-10-02 10:05
# update_at: 2026-10-02 10:05

import sys


def inv_mod(a: int, b: int) -> int:
    """扩展欧几里得求逆元：返回最小正整数 x，使 a·x ≡ 1 (mod b)。

    不变量：余数 r0 ≡ 系数 s0 · a (mod b)。辗转相除结束时 r0 = gcd(a, b) = 1，
    于是 s0 就是 a 的一个逆元；对 b 取模落到 [0, b) 即最小正整数解。
    """
    r0, r, s0, s = a, b, 1, 0
    while r:
        q = r0 // r
        r0, r = r, r0 - q * r   # 标准辗转相除
        s0, s = s, s0 - q * s   # 系数同步消去，维持上面的同余不变量
    return s0 % b


def solve() -> None:
    a, b = map(int, sys.stdin.buffer.read().split())
    print(inv_mod(a, b))


if __name__ == "__main__":
    solve()

复杂度

• 时间：$O(\log \min(a, b))$。核心是欧几里得辗转相除，余数按斐波那契速率下降，最坏约 $\log_\varphi \min(a, b)$ 轮，$2 \times 10^9$ 规模下不超过约 45 轮；与 C++ 正解同阶。真实数据实测单例约 $0.02\text{s}$（时限 $1000\text{ms}$）。
• 空间：$O(1)$，只用四个整数变量；峰值内存约 $14.6\text{MB}$（限制 $32\text{MB}$）。

总结

• 同余方程 $ax \equiv 1 \pmod b$ 与不定方程 $ax + by = 1$ 等价；"保证有解"即保证 $\gcd(a, b) = 1$，逆元一定存在。
• 扩展欧几里得在辗转相除时同步维护系数，不变量是 $r_0 \equiv s_0 \cdot a \pmod b$；终止时 $r_0 = 1$，系数 $s_0$ 即一个逆元。
• 负系数对 $b$ 取模折回 $[0, b)$，由解的唯一性这正是最小正整数解。
• 朴素枚举 $O(b)$ 在 $b = 2 \times 10^9$ 时不可行，扩展欧几里得 $O(\log b)$ 一步消除瓶颈——这是"把试探换成代数结构"的经典收益。