ExGCD:
目的：求形如 \(Ax+By=C\) 的不定方程的通解
有解判断：
方程有解的充要条件是 \(Gcd(a,b)|C\)，可以使用数论知识证明
问题简化：
将问题简化为求 \(Ax+By=Gcd(a,b)\) 的通解，先求他的一组解。
思路及证明：
使用递归的思想减小A和B的值，直至方程变为\(x=Gcd(x,0)\)的形式。
已知：
\[Gcd(a,b)=Gcd(b,a\%b) \]考虑：
\[Ax_1+By_1=Gcd(A,B) \]\[Bx_2+(A\%B)y_2=Gcd(B,A\%B) \]然后寻找\((x_1,y_1)\)和\((x_2,y_2)\)的递推关系。
将\(a\%b=\lfloor\frac{a}{b}\rfloor b\)带入得：
\[A(x_1-y_2)+B(y_1-x_2+\lfloor\frac{A}{B}\rfloor y_2)=0 \]由于我们只需要每个递归状态的一组解即可，所以我们可以直接使用
\(x_1=y_2\)
\(y_1=x_2-\lfloor\frac{A}{B}\rfloor y_2\)
进行递归，得到一组特解。
求通解：
已知：
\[Ax_1+By_1=C \]\[Ax_2+By_2=C \]两式做差：
\[Ax_1+By_1=Ax_2+By_2 \]设\(g=Gcd(A,B)\)
则：
\[\frac{A}{g}(x_1-x_2)+\frac{B}{g}(y_1-y_2)=0 \]得通解：
\(x=x_0+k\frac{B}{g}\)
\(y=y_0-k\frac{A}{g}\)
例题：
青蛙的约会
本题需要求出x的最小正整数解，可以采用\(M=|\frac{B}{g}|\), \(x=(x_0%M+M)%M\)来求出最小整数解x，注意模数一定取正数！还有注意开longlong
#include<bits/stdc++.h>
#define int long long
using namespace std;
int x, y;
int exgcd(int a, int b){
if (b == 0){
x = 1;y = 0;return a;
}
int g = exgcd(b, a%b);
int tmp = x;
x = y;
y = tmp - a / b * y;
return g;
}
signed main(){
int x0, y0, m, n, l;cin>>x0>>y0>>m>>n>>l;
int g = exgcd(m - n, l);//方程形如(m-n)x+ly=(y0-x0)
if((y0 - x0) % g) cout<<"Impossible"<<endl;
else{
x *= (y0 - x0) / g;
l = abs(l / g);
x = (x % l + l) % l;
cout<<x<<endl;
}
return 0;
}