Lib/拡張ユークリッド

code:cpp

pair<long long, long long> extgcd(long long a, long long b) {

if (b == 0) return make_pair(1, 0);

long long x, y;

tie(y, x) = extgcd(b, a % b);

y -= a / b * x;

return make_pair(x, y);

}

ax + by = gcd(x,y) なるa,bをlogNで求める

b=0のとき→gcd(a,0) = a なので　自明に{1,0}

それ以外のとき→

a = qb + rで表す → extgcd(b,r)を解く