我们在遇见不定方程的时候，总会一筹莫展，但是EXGCD为我们提供了方法，如同
$ a x + b y = c $
那么我们先从这个这个式子出发：
$ax+by=gcd(a,b)$ $(1)$
我们不妨设出另一个式子
$ b x_{0}+(a \%\ b)y_{0}=gcd(b,a \%\ b)$ $(2)$
Because $gcd(a,b)= gcd ( b , a \%\ b ) $ ,thus:
\(a x+b y=bx_{0}+a \%\ b y_{0}\)
\(a x+b y=bx_{0} +(x-a/b \times y_{0})\)
\(a x+b y=ay_{0} +b(x-a/b \times y_{0})\)
根据乘法等式，相对应系数的未知数相等，那么就可以得到：
$x=y_{0} y=x-a/b*y_{0}$
那么在求gcd的过程中，我们可以在其中不断求解，但是递归到底时返回的x，y值是多少？
我们令在b=0时，带入（1）式，那么得到
$ax = a$,我们令x=1,y=0即可。
然后思考如何求解一开始的那个式子：
若有$ax+by=c$，则设$ax_{0}+by_{0}=c$,
两式相减：$a(x-x_{0})+b(y-y_{0})=0$
移项，除以gcd(a,b):$\frac{a}{gcd(a,b)}(x-x_{0})= - \frac{b}{gcd(a,b)}(y-y_{0})$
因为$gcd(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})=1$
所以$\frac{b}{gcd(a,b)}$可以整除$(x-x_{0})$
即 $\frac{b}{gcd(a,b)} \times t=(x-x_{0}), t \in Z$
对于任意x，都可以表示为
$x=x_{0}+\frac{b}{gcd(a,b)}$
那么根据exgcd求出的特解且$t \in Z$，我们可以这样求出最小解：
$x_{min}=x \%\(\frac{b}{gcd(a,b)})$
在代码中的写法可以是
mod=b/gcd(a,b),ans=(x%mod+mod)%mod
那么这样我们就解决了$ax+by=gcd(a,b)$最小解问题。
如果是$ax+bx=c$，只需要两边乘上$\frac{c}{gcd(a,b)}$即可；
这里附上 例题
并给出模板Code：
#include<bits/stdc++.h> using namespace std; int n,m,L,t1,t2; 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;//return gcd } int main(){ scanf("%d%d%d%d%d",&t1,&t2,&n,&m,&L); int x,y; if(m<n) swap(m,n),swap(t1,t2);//由于exgcd函数默认a，b为正整数，所以要换一下 int gcd=exgcd(m-n,L,x,y); cerr<<x*((t1-t2)/gcd)<<endl; if((t1-t2)%gcd!=0) printf("Impossible\n"); //根据推论，应当满足等式两端成立 else printf("%lld\n",(1ll*x*((t1-t2)/gcd)%(L/gcd)+L/gcd)%(L/gcd));//正负处理 }
这里给出定理的内容，我大概描述一下：
对于$a,b$两个整数,且$gcd(a,b)=d$，那么对于任意的$x,y ,ax+by$是d的倍数。
转载于:https://www.cnblogs.com/waterflower/p/11331717.html
相关资源：JAVA上百实例源码以及开源项目