证明链接：http://blog.csdn.net/lincifer/article/details/49391175
模板：
int exGcd(int a,int b,int &x,int &y) { if(b==0) { x=1;y=0; return a; } int r=exGcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; return r; }
证明链接：http://blog.csdn.net/lincifer/article/details/49391175
模板：
int exGcd(int a,int b,int &x,int &y) { if(b==0) { x=1;y=0; return a; } int r=exGcd(b,a%b,x,y); int t=x;x=y;y=t-a/b*y; return r; }
原文：https://www.cnblogs.com/TQCAI/p/8455447.html