1632：【 例 2】[NOIP2012]同余方程

题目描述

求关于 $x$ 的同余方程 $a x \equiv 1 \pmod{b}$ 的最小正整数解。

输入格式

输入只有一行，包含两个正整数 $a,b$，用一个空格隔开。

输出格式

输出只有一行，包含一个正整数 $x_0$，即最小正整数解。输入数据保证一定有解。

样例

样例输入 #1

3 10

样例输出 #1

7

样例解释 #1

• 方程：$3x \equiv 1 \pmod{10}$。
• 验证：$3 \times 7 = 21$，$21 \bmod 10 = 1$，所以 $x=7$ 是解。
• 最小正整数解就是 $7$。

数据范围

• 对于 $40\%$ 的数据，有 $2 \le b \le 1000$；
• 对于 $60\%$ 的数据，有 $2 \le b \le 50000000$；
• 对于 $100\%$ 的数据，有 $2 \le a, b \le 2000000000$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题是求解线性同余方程 $ax \equiv 1 \pmod{b}$ 的最小正整数解。这等价于求 $a$ 在模 $b$ 意义下的乘法逆元。因为方程有解当且仅当 $\gcd(a,b)=1$（即 $a$ 与 $b$ 互质）。题目保证有解，所以 $\gcd(a,b)=1$。

可以使用扩展欧几里得算法（exgcd）求解。扩展欧几里得算法用于求解方程 $ax + by = \gcd(a,b)$ 的一组整数解 $(x,y)$。由于 $\gcd(a,b)=1$，方程 $ax + by = 1$ 有解，取模 $b$ 可得 $ax \equiv 1 \pmod{b}$，所以 $x$ 就是 $a$ 模 $b$ 的逆元。注意求出的 $x$ 可能是负数，需要调整为最小正整数解：$x = (x \bmod b + b) \bmod b$。

具体步骤：

1. 使用 exgcd 求解 $ax + by = 1$ 的一组解 $(x,y)$。
2. 最小正整数解为 $(x \bmod b + b) \bmod b$。

注意：$a,b$ 最大 $2\times 10^9$，计算过程中可能溢出，需要使用 long long 类型。

扩展欧几里得算法模板：

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