拡張ユークリッドの互除法 (Extended Euclidean algorithm)
(src/math/ExtGCD.hpp)

• View this file on GitHub
• Last update: 2024-06-01 02:08:16+09:00
• Include: #include "src/math/ExtGCD.hpp"

• 参考実装：KACTL

使い方

• ll extgcd(ll a, ll b, ll& x, ll& y)：$\text{gcd}(a, b)$ を返す．$(x, y)$ には，$ax + by = \text{gcd}(a, b)$ の整数解であって $|x| + |y|$ が最小のものが代入される．
  • $O(\log(x + y))$ 時間

使い方 (応用)

• モジュロ逆元 modinv(a, mod) を求める：extgcd(a, mod, x, y) をすると a * x + mod * y == 1 になるので，x が a のモジュロ逆元である．

ソラ書きしてみよう

$(1, 0, a)$ と $(0, 1, b)$ に対してユークリッドの互除法をするとできる．

array<ll, 3> extgcd(ll a, ll b) {
    array<ll, 3> A = {1, 0, a}, B = {0, 1, b};
    while(B[2]) {
        ll q = A[2] / B[2];
        rep(i, 0, 3) A[i] -= B[i] * q;
        swap(A, B);
    }
    return A;
}

Verified with

• test/math/ExtGCD.test.cpp

Code

// returns gcd(a, b) and assign x, y to integers
// s.t. ax + by = gcd(a, b) and |x| + |y| is minimized
ll extgcd(ll a, ll b, ll& x, ll& y) {
   // assert(a >= 0 && b >= 0);
   if(!b) return x = 1, y = 0, a;
   ll d = extgcd(b, a % b, y, x);
   y -= a / b * x;
   return d;
}

#line 1 "src/math/ExtGCD.hpp"
// returns gcd(a, b) and assign x, y to integers
// s.t. ax + by = gcd(a, b) and |x| + |y| is minimized
ll extgcd(ll a, ll b, ll& x, ll& y) {
   // assert(a >= 0 && b >= 0);
   if(!b) return x = 1, y = 0, a;
   ll d = extgcd(b, a % b, y, x);
   y -= a / b * x;
   return d;
}

Back to top page