對于$a?x+b?y=c$,這樣一個二元一次方程組，我們想要得到他的一組解可以用擴展歐幾里得算法，參數列表的a,b,x,y就是方程中的a,b,x,y，d計算出來是gcd(a,b)。

算法求出來的是$a?x+b?y=gcd(a,b$的一組解，解系可以表示為$X=x+b/d?k,Y=y?a/d?k$，k為任意整數

但是我們要求解的是$a?x+b?y=c$

方程組有解的充分必要條件是$d|c$，正確性很容易證明

在確定方程組優解以后$c/d?X,c/d?Y$為方程組的一組解系

需要注意的是這樣得到的不是方程組的所有的解

例如：對于方程$3x+y=60$,$17?3+9?1=60$顯然為一組解，但是我們卻沒有辦法用過擴展歐幾里得算法得到這組解。所以凡是對x,y有限制條件（不是指正負，而是要求和不能超過多少等條件）我們要考慮是否能夠使用擴展歐幾里得算法，相反，如果對x,y具體大小沒有過多限制，而是僅僅說明要求正負等條件時就可以使用擴展歐幾里得算法。

void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y)
{if(!b){d=a; x=1; y=0;}else {gcd(b,a%b,d,y,x); y-=x*(a/b);}
}

下面簡單證明一下正確性。

令c=a%b=a-k*b (k=a/b)
$a?x1+b?x2=gcd(a,b)$ $b?x2+c?y2=gcd(b,c)$
有最大公因數的性質我們知道$gcd(a,b)=gcd(b,c)$
所以我們得到等式$a?x1+b?y1=b?x2+c?y2=b?x2+a?y2?k?b?y2$
其中的一組解為$x1=y2,y1=x2?k?y2,其中k=a/b$，因此我們可以遞歸的求解，終止遞歸的條件為c==0，則這個時候的b為gcd(a,b)，解為x=1,y=0，然后遞歸的返回（這個時候再看代碼應該就能理解了，代碼實現很巧妙）

為了快速得到非負的X,可以稍微處理一下：X=(X%B’+B’)%B’，這樣得到的就應該是最小的非負X了
（B’=B/D）

簡單的例題hihoCoder#1297

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<ctime>
#include<climits>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAXN=1e5+5;ll s1,s2,v1,v2,m;void ex_gcd(ll A,ll B,ll& D,ll& x,ll& y)
{if(!B){D=A; x=1; y=0;}else{ex_gcd(B,A%B,D,y,x);y-=(A/B)*x;}}int main()
{while(~scanf("%lld%lld%lld%lld%lld",&s1,&s2,&v1,&v2,&m)){ll A=v1-v2,B=m,C=s2-s1,D,x,y;if(A<0){A=-A; C=-C;}C=(C%m+m)%m;ex_gcd(A,B,D,x,y);if(C%D){printf("-1\n");continue;}B/=D;x=C/D*x;x=(x%B+B)%B;printf("%lld\n",x);}return 0;
}