扩展bmdlz定理用于解方程 ax + by = 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, x, y); int t = x; x = y; y = t - (a / b) * y; return d;}证明见：https://oi-wiki.org/math/gcd/
通过bmdlz定理构造等价的方程，进行递归求解；
线性同余方程：
形如 ax ≡ c（mod b）的方程；
1. 等价： 等价于 ax + by = c ，两边同时取余就一样了
2. 判定条件：exgcd 可求 ax + by = gcd（a，b）的解 ，所以c是gcd（a，b）的整数倍时，时方程ax + by = c 有解
3. 通解： 求解后可根据原方程构造通解： x + k*b/gcd ，y - k*a/gcd
4.最小正整数解： 根据通解的形式 ，可得x的最小正整数解为 （x%t + t）%t ，t = b/gcd；
int ex_gcd(int a, int b, int& x, int& y) { if (b == 0) { x = 1; y = 0; return a; } int d = ex_gcd(b, a % b, x, y); int temp = x; x = y; y = temp - a / b * y; return d;}bool liEu(int a, int b, int c, int& x, int& y) { int d = ex_gcd(a, b, x, y); if (c % d != 0) return 0; int k = c / d; x *= k; y *= k; return 1;}
转载于:https://www.cnblogs.com/-ifrush/p/11350165.html