題目

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;
}