numtheory/exgcd.cpp

• View this file on GitHub
• Last update: 2024-01-24 20:41:29+08:00

Code

//source: KACTL
//note: inv calculate modulo inverse of r mod m where gcd(r, m) = 1

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;
}

ll inv(ll r, ll m) {
  ll x, y;
  ll gcd = euclid(r, m, x, y);
  assert(gcd == 1);
  return (x % m + m) % m;
}

#line 1 "numtheory/exgcd.cpp"
//source: KACTL
//note: inv calculate modulo inverse of r mod m where gcd(r, m) = 1

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;
}

ll inv(ll r, ll m) {
  ll x, y;
  ll gcd = euclid(r, m, x, y);
  assert(gcd == 1);
  return (x % m + m) % m;
}

Back to top page