扩展欧几里得
欧几里得：
1 void gcd(int a, int b) { 2 return gcd(b, a % b); 3 }
扩展欧几里得：
根据裴蜀定理可以求出ax+by=c的直线上的所有整数解。
裴署定理：设a,b是不全为零的整数，则存在整数x,y, 使得ax+by=gcd(a,b) .
存在x和y使得ax+by=gcd(a,b)成立，而根据辗转相除法，方程最终态为a=gcd(a,b)，b=0，此时x=1，y=0，将此解迭代回去即可求出x与y的最初解。
int exgcd(int a,int b,int &x,int &y) { if(!b){ x=1;y=0;return a; } int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; }
返回值为a与b的最大公约数