资讯详情

gcd与exgcd

inline int gcd(int a, int b) { return b == 0 : a ? gcd(b, a % b); }
inline ll exgcd(ll a, ll b, ll &x, ll &y) {if (b == 0) { x = 1, y = 0; return a; }ll d = exgcd(b, a % b, x, y);ll z = x; x = y; y = z - y * (a / b);return d;
}