作算法題時，經(jīng)常遇到的一個問題就是求AX+BY=C的問題。窮舉法往往因為耗時太多而變得不可行，因此需要一些算法來進行優(yōu)化。
比較常見的就是擴展的歐幾里得算法，簡單整理和總結(jié)如下
定理1：若gcd(A, B)大于1且不能整除C，則該方程不存在整數(shù)解。
證明：反證法，若存在整數(shù)X1，Y1，使得AX1+BY1=C，且C不能被gcd(A,B)（設(shè)為D）整除
C=AX1+BY1=(A/D)*D*X1+(B/D)*D*Y1=(A/D*X1+B/D*Y1)*D，顯然與假設(shè)矛盾，因此得證。
根據(jù)定理1，當(dāng)gcd(A,B)大于1，且可以整除C的時候，可以先將兩邊同除以gcd(A,B），得到A'X+B'Y=C'，該方程與原方程同解。因此，接下來我們僅討論gcd(A,B)為1的情況。
對于這種情況，可以先求出AX+BY=1的解(X0,Y0)，接著就可以得知(C*X0,C*Y0)就是原方程的解了。
定理2：A，B的所有公約數(shù)D，均可以整除AX+BY
證明略，比較簡單
推論2.1：A，B的最大公約數(shù)，是集合S{V| V>0, V=AX+BY}中最小的一個數(shù)
證明： 因為所有的公約數(shù)一定能整除最大公約數(shù)，所以gcd(A，B）一定屬于集合S，另外，gcd(A,B)能整除S中的任意成員，因此gcd(A,B)只能是該集合中的最小數(shù)。
根據(jù)推論2.1，解方程AX+BY=1，和求解A，B的最大公約數(shù)有很大的關(guān)系
根據(jù)歐幾里得定理，若a>b, 則gcd(a, b)=gcd(b, a%b)，因此作如下擴展
AX+BY=BX1+(A%B)Y1，展開左邊的A，可以得到(A/B*B+A%B)X+BY=BX1+(A%B)Y1，
不妨取X=Y1，則可以得到Y(jié)=X1-(A/B)Y1，對應(yīng)的代碼
/***擴展的歐幾里德算法a*x + b*y = Gcd(a,b)的一組整數(shù)解，結(jié)果存在x,y中***/
void extend_gcd(long long a, long long b, long long& x, long long &y) {
if(b == 0) {
x = 1;
y = 0;
return;
}
extend_gcd(b, a % b, x, y);
long long tmp = x;
x = y;
y = tmp - a / b * y;
}
當(dāng)求得了AX+BY=C的一個解(X1,Y1)后，可以進一步得到其余的解的形式如下
X=X1+B*t
Y=Y1-A*t，其中t為整數(shù)
至此，方程AX+BY=C的整數(shù)解求出。