同余方程

同余方程 T3 https://www.luogu.com.cn/problem/P1082

题目描述

求关于 $x$ 的同余方程 $ax\equiv 1(\mathrm{mod}b)$ 的最小正整数解。

输入格式

一行，包含两个整数 $a,b$，用一个空格隔开。

输出格式

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

样例 #1

样例输入 #1

3 10

样例输出 #1

7

提示

数据规模与约定

• 对于 $40$ 的数据，$2\le b\le 1,000$；
• 对于 $60$ 的数据，$2\le b\le 50,000,000$；
• 对于 $100\%$ 的数据，$2\le a,b\le 2,000,000,000$。

思路

$ax\equiv 1(\mathrm{mod}b)$ 求最小的 x 正整数解。

式子等价于 $ax+by=1$ ， 故直接用扩展欧几里得定理（因为1可以是任何数的约数）得出 $x_0,y_0$。

而其所有解为： $x=x_0+k\frac{b}{d}=x_0+kb$ $y=y_0-k\frac{a}{d}=y_0-ka$

其在 b 范围内的最小正整数解为 $(x_0+b)\mathrm{mod}b$ 。

代码

#include <bits/stdc++.h>
using namespace std;
 
int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a/b * x;
    return d;
}
 
void solve() {
    int a, b, x, y;
    cin >> a >> b;
    exgcd(a,b,x,y);
 
    cout << (x + b) % b << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}