扩展欧几里得算法

前提了解：

裴蜀定理：对于任意a，b，一定存在x,y，使a*x+b*y=gcd(a,b);
对于a*x+b*y=c当且仅当c%gcd(a,b)==0时才有解

下面利用扩展欧几里得算法求解a*x+b*y=gcd(a,b)中的x,y
扩展欧几里得算法其实就是欧几里得算法的扩充
欧几里得算法最后结束的条件是b=0

当b=0

此时  a*x+b*y=gcd(a,b)          //gcd(a,b)=a
等价于a*x    =a
显然此时x=1,y=0

当b!=0

gcd(a,b)=gcd(b,a%b)
由裴蜀定理
b*x'+a%b*y'=gcd(b,a%b)
等价于b*x'+(a-a/b*b)*y'=gcd(b,a%b)
将a,b都单独提出,整理得
a*y'+b(x'-a/b*y')=gcd(b,a%b)=gcd(a,b)       //c++中/是下取整
即x=y',y=x'-a/b*y'
因此采用递归，先求出下一层的x',y'，再利用下一层的x',y',即可求出上一层的x,y
刚好可以利用欧几里得算法实现

参考 https://www.acwing.com/solution/content/1393/