int gcd(int a,int b) { return b == 0? a : gcd(b,a%b); }
//返回最大公约数 //ax+by=gcd(a,b)，求x,y int exgcd(int a,int b,int &x,int &y) { int d = a; if(b != 0) { d = exgcd(b,a%b,y,x); y -= (a/b) * x; } else{x = 1;y = 0;} return d; }
原文：https://www.cnblogs.com/Asurudo/p/10599270.html
