当需找出一对整数(x,y)使得ax+by=gdc(a,b)时,可使用扩展欧几里得算法;
注意,a需大于b,当a<0时需|a|x+by=gdc(|a|,b)
void gcd(int a,int b,int& x,int& y){ if(!b) { x=1; y=0; return a; } else { int r=gcd(b,a%b,x,y) int t=x; x=y; y=t-y*(a/b); return r; }}
若方程ax+by=c的一组整数解为(x,y),则它的任意整数解都可以写成(x+kb,x+ka),其中a=a/gcd(a,b),b=b/gcd(a,b),k取任意整数;
当c是gcd(a,b)的倍数时才有解;