扩展欧几里得算法

扩展欧几里得算法 裴蜀定理：对于任意正整数 $a、b$ ，一定存在非零整数 $x、y$ ，使得 $ax + by = (a, b)$ （最大公约数） 1.AcWing877.扩展欧几里得算法123456789101112131415161718192021222324252627282930313233#include<iostream>using namespace std;// (a, b) = (b, a mod b)// return b ? gcd(b, a % b) : a;int gcd(int a, int b) { if (!b) return a; return gcd(b, a % b);}// ax + by = (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;}int main() { int m; scanf("%d", &m); while (m--) { int a, b, x, y; scanf("%d%d", &a, &b); exgcd(a, b, x, y); printf("%d %d\n", x, y); } return 0;} 2.AcWing878.线性同余方程 给定$a、m、b$，求一个整数 $x$ 使得 $ax≡b(mod~m)$ 1234567891011121314151617181920212223242526272829303132333435#include<iostream>using namespace std;// (a, b) = (b, a mod ...