作算法题时，经常遇到的一个问题就是求AX+BY=C的问题。穷举法往往因为耗时太多而变得不可行，因此需要一些算法来进行优化。
比较常见的就是扩展的欧几里得算法，简单整理和总结如下
定理1：若gcd(A, B)大于1且不能整除C，则该方程不存在整数解。
证明：反证法，若存在整数X1，Y1，使得AX1+BY1=C，且C不能被gcd(A,B)（设为D）整除
C=AX1+BY1=(A/D)*D*X1+(B/D)*D*Y1=(A/D*X1+B/D*Y1)*D，显然与假设矛盾，因此得证。
根据定理1，当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的所有公约数D，均可以整除AX+BY
证明略，比较简单
推论2.1：A，B的最大公约数，是集合S{V| V>0, V=AX+BY}中最小的一个数
证明： 因为所有的公约数一定能整除最大公约数，所以gcd(A，B）一定属于集合S，另外，gcd(A,B)能整除S中的任意成员，因此gcd(A,B)只能是该集合中的最小数。
根据推论2.1，解方程AX+BY=1，和求解A，B的最大公约数有很大的关系
根据欧几里得定理，若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=X1-(A/B)Y1，对应的代码
/***扩展的欧几里德算法a*x + b*y = Gcd(a,b)的一组整数解，结果存在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;
}
当求得了AX+BY=C的一个解(X1,Y1)后，可以进一步得到其余的解的形式如下
X=X1+B*t
Y=Y1-A*t，其中t为整数
至此，方程AX+BY=C的整数解求出。