概述
【背景：欧几里得算法即辗转相除法 求gcd（a,b）】
对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整
数对 x，y ，使得 gcd（a，b）=ax+by。
递归式推导
根据gcd(a,b)=gcd(b,a%b)
可得ax+by=bx'+(a%b)y'
而a%b=a-b*k（k=a/b）
所以ax+by
=bx'+[a-b*(a/b)]y'
可以得到x与x'相关，y与y'相关
这样就构造出了递归式
递归终点
在欧几里得算法求gcd时，递归终点是b=0
此时ax=gcd(a,0) 所以x=1，即为递归终点
代码实现
int exgcd(int a,int b,int &x,int &y){//求特解 if(b==0){ x=1,y=0; // return a;//gcd } exgcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-(a/b)*y; }
通解与特解
若（x0，y0）是不定整数方程ax+by=c的一组解，则他的任意整数解都可以表示成（x0+kb', y0-ka'）
其中a'=a/gcd(a,b), b'= b/gcd(a,b).