拓展欧几里得的模板
ll exgcd(ll a, ll b, ll &x, ll &y) //求得这层的x，y (x,y是前的&是引用的意思) { if(b == 0) {x = 1; y = 0; return a;} // 最底层 ll d = exgcd(b, a%b, y, x); // 这层的x是下层的y y = y - a/b * x; //利用下层的x,y求得这层的y return d; }
int gcd(ll a,ll b) { a = abs(a),b = abs(b); while (b) { int c = b; b = a % b; a = c; } return a; }
