扩展欧几里得 exgcd
求解形如 \(a\cdot x + b\cdot y = \gcd(a,b)\) 的不定方程的任意一组解。
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;
}
例题：求解二元一次不定方程 \(A\cdot x + B\cdot y = C\) 。
auto clac = [&](int a, int b, int c) {int u = 1, v = 1;if (a < 0) { // 负数特判，但是没用经过例题测试a = -a;u = -1;}if (b < 0) {b = -b;v = -1;}int x, y, d = exgcd(a, b, x, y), ans;if (c % d != 0) { // 无整数解cout << -1 << "\n";return;}a /= d, b /= d, c /= d;x *= c, y *= c; // 得到可行解ans = (x % b + b - 1) % b + 1;auto [A, B] = pair{u * ans, v * (c - ans * a) / b}; // x最小正整数 特解ans = (y % a + a - 1) % a + 1;auto [C, D] = pair{u * (c - ans * b) / a, v * ans}; // y最小正整数 特解int num = (C - A) / b + 1; // xy均为正整数 的 解的组数
};