euclid

Finds two integers x and y, such that ax+by=gcd(a,b). If you just need gcd, use the built in __gcd instead. If a and b are coprime, then x is the inverse of a (mod b).

5 lines

content/number-theory/euclid.h — Unknown, source: predates tinyKACTL

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, a;
	ll d = euclid(b, a % b, y, x);
	return y -= a/b * x, d;
}