ALDS1_1_B:

最大公約数

最大公約数を求める素朴なアルゴリズムは次のようになります。

gcd(x, y)
    n = min(x, y)
    for d = n downto 1
        if x と y がともに d で割り切れる
            return d

このアルゴリズムは、$x$ と $y$ の小さい方を $n$ とし、$d$ が $n$ から 1 までについて、$x$ と $y$ の両方を割り切れるかを調べ、割り切れたら $d$ を返します。

このアルゴリズムは、正しい出力を行いますが最悪 $n$ 回の割り算を行う必要があるため、大きな数に対しては時間内に出力を得ることはできません。

ユークリッドの互除法は「$x \geq y$ のとき $gcd(x, y)$ と $gcd( y, x を y で割った余り)$ は等しい」という定理を用いて $x$ と $y$ の最大公約数を高速に求めるアルゴリズムです。

例えば、54 と 20 の最大公約数は以下のように求めることができます。
$gcd(54, 20)$
$= gcd(20, 14)$
$= gcd(14, 6)$
$= gcd(6, 2)$
$= gcd(2, 0)$
$= 2$

$gcd(a, b)$ において、$b$ が 0 になったときの $a$ が、与えらえた整数 $x$ と $y$ の最大公約数となります。

ここで、このアルゴリズムが正しいことを、$a$ と $b$ の公約数と $b$ と $r\; (a$ % $b)$ の公約数が等しいことを示して確認します。$d$ を $a$ と $b$ の公約数とすると、自然数 $l$、$m$ を用いて $a = ld$、$b = md$ と表すことができます。$a = bq + r$ に $a = ld$ を代入し $ld = bq + r$ を得ます。これに、$b = md$ を代入して、$ld = mdq + r$、これをまとめると $r = (l − mq)d$ が得られます。この式は $d$ が $r$ の約数であることを示しています。また、$d$ は $b$ を割り切るので、$d$ は $b$ と $r$ の公約数になります。一方、同様の方法で、$d'$ が $b$ と $r$ の公約数なら $d'$ は $a$ と $b$ の公約数であることが分かります。よって $a$ と $b$ の公約数の集合と、$b$ と $r$ の公約数の集合は等しく、最大公約数も等しくなります。

ユークリッドの互除法のアルゴリズムは次のように実装することができます。

gcd(x, y)
    if x < y
        swap(x, y)
    while y > 0
        r = x % y
        x = y
        y = r

    return x

ユークリッドの互除法の計算量を見積もってみましょう。例えば、74 と54 に gcd を適用していくと $a = bq + r$ は

$74 = 54 \times 1 + 20(= r_1)$
$54 = 20 \times 2 + 14(= r_2)$
$20 = 14 \times 1 + 6(= r_3)$
$14 = 6 \times 2 + 2(= r_4)$
$6 = 2 \times 3 + 0(= r_5)$
:

のようになります。ここで gcd を適用して得られる列 $b = r_1, r_2, r_3, ...$ がどのように減っていくかを考えます。$a = bq + r (0 < r < b)$ とすると、$r < a/2$ より、$r_{i+2} < r_i/2$ が成り立ちます。このことより、ユークリッドの互除法は多くとも $2log_2(b)$ で完了するので、$O(log\; b)$ と見積もることができます。

Reference

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 (マイナビ) AIZU ONLINE JUDGE のコース問題を題材にした解説書です。初級者が体系的にアルゴリズムとデータ構造の基礎を学ぶことができる入門書となっています。