题目

203. 同余方程

算法标签: 数论, 扩展欧几里得算法

思路

简单的扩展欧几里得算法应用题, 扩展欧几里得算法可以直接计算同余方程的通解, 因为求得是最小正整数解, 因此需要取模转换为正整数
$$ax+by\equiv 1$$

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int a, b;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> a >> b;
    int x, y;
    exgcd(a, b, x, y);
    
    cout << (x % b + b) % b << "\n";
    return 0;
}