拡張ユークリッドの互除法

概要

$ax + by = \gcd(a,b)$ なる $x,y$ をユークリッドの互除法の過程から計算する．

ユークリッドの互除法では $g = \gcd(a,b) = \gcd(b,a \% b)$ という事実に基づいて $g$ を求めるが，この再帰の前後で，ある $x,y,x',y'$ が存在して $ax + by = bx' + (a\%b)y' = g$ を満たす． $a\%b = a-b\lfloor a/b \rfloor$ を代入すると $ax + by = bx' + (a-b\lfloor a/b \rfloor) y' = ay'+b(x'-\lfloor a/b \rfloor y')$．係数を比較して $x = y', y = x'-\lfloor a/b \rfloor y'$ を得る．

非再帰版は週刊 spaghetti_source を参照．

計算量

$O(\log(\min(a,b)))$

使い方

extgcd(a,b,x,y)

$ax + by = \gcd(a,b)$ を満たす $x,y$ を求める．解を代入する変数 $x$, $y$ を参照型で渡す．戻り値は $\gcd(a,b)$．

実装

あり本版

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

// 非再帰版
// ll extgcd(ll a, ll b, ll &x, ll &y) {
//     for (ll u = y = 1, v = x = 0; a;) {
//         ll q = b / a;
//         swap(x -= q * u, u);
//         swap(y -= q * v, v);
//         swap(b -= q * a, a);
//     }
//     return b;
// }

std::tuple<ll, ll, ll> extgcd(ll a, ll b) {
    ll x, y;
    ll g = extgcd(a, b, x, y);
    return std::make_tuple(x, y, g);
}

参考文献

アルゴリズムイントロダクション 31.2 (p.778)