扩展欧几里得 求解不定方程 ax+by=gcd(a, b) 的整数解
对于方程 ax+by=c, 如果 gcd(a, b)|c, 则有解, 解为 ax+by=gcd(a, b) 的解乘以 c/gcd(a, b); 否则无解
long long exgcd(long long a, long long b, long long& x, long long &y)
{
if (!b)
{
x = 1;
y = 0;
return a;
}
long long t = exgcd(b, a%b, y, x);
y -= a / b * x;
return t;
}
