题目分析

本题要求解线性同余方程 $ax \equiv 1 \pmod{b}$，其中 $a$ 和 $b$ 是给定的正整数，且保证有解（即 $\gcd(a,b) = 1$）。

解题思路

这个方程实际上是在求 $a$ 在模 $b$ 意义下的乘法逆元 $x$，即 $x \equiv a^{-1} \pmod{b}$。由于题目保证 $\gcd(a,b) = 1$，因此可以使用扩展欧几里得算法求解。

扩展欧几里得算法原理

扩展欧几里得算法用于求解方程 $ax + by = \gcd(a,b)$。当 $\gcd(a,b) = 1$ 时，方程变为 $ax + by = 1$。对两边同时取模 $b$，得到 $ax \equiv 1 \pmod{b}$。因此，我们求得的 $x$ 就是原方程的解。

算法步骤

1. 使用扩展欧几里得算法求出 $ax + by = 1$ 的一组解 $(x_0, y_0)$
2. 由于解不唯一，需要将 $x_0$ 调整到最小正整数解：$x = (x_0 \bmod b + b) \bmod b$

代码实现分析

#include <bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

int main() {
    int a, b, x, y;
    cin >> a >> b;
    exgcd(a, b, x, y);
    cout << ((x % b) + b) % b; // 求ax+by=1的最小x正整数解
    return 0;
}

代码解析

• exgcd函数：递归实现扩展欧几里得算法

  • 基准情况：当 $b = 0$ 时，$x = 1$，$y = 0$，返回 $a$
  • 递归调用：计算 $\gcd(b, a \bmod b)$，同时交换 $x$ 和 $y$ 的位置
  • 更新公式：$y = y - \lfloor a/b \rfloor \times x$

• 主函数：

  • 读入 $a$ 和 $b$
  • 调用 exgcd 求解 $ax + by = 1$
  • 输出最小正整数解：$((x \bmod b) + b) \bmod b$

复杂度分析

• 时间复杂度：$O(\log \min(a,b))$，扩展欧几里得算法的时间复杂度与欧几里得算法相同
• 空间复杂度：$O(\log \min(a,b))$，递归调用栈的深度

示例验证

对于样例输入：3 10

扩展欧几里得算法求解过程：

• 求解 $3x + 10y = 1$
• 求得 $x = 7$，$y = -2$
• 验证：$3 \times 7 = 21 \equiv 1 \pmod{10}$

输出：7

总结

本题是经典的数论问题，核心在于理解扩展欧几里得算法的原理和应用。通过求解贝祖等式 $ax + by = \gcd(a,b)$，当 $\gcd(a,b) = 1$ 时，得到的 $x$ 就是 $a$ 在模 $b$ 意义下的逆元，再通过模运算调整即可得到最小正整数解。