ユークリッドの互除法

2019年12月6日数学最大公約数,競プロ,ユークリッドの互除法,拡張ユークリッドの互除法

2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。

このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られています。

Input: gcd(48,32)
Output: 16

アルゴリズム

ユークリッドの互除法 (gcd(a,b)):

  1. b が 0 ならば、a を返す
  2. b が 0 でなければ、gcd(b, a%b) を返す

※ 原理としては単純で、「 a と b の最大公約数」と「 b と a割るbの余り の最大公約数」が等しくなることを利用しています。

※ a,bの大小関係は考慮していません。最初の入力が b>a であったとしても、一度gcdを再帰的に呼び出したら、gcd(b,a)と順番が入れ替わることに注意してください。

計算量

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

ユークリッドの互除法をのステップを2回行ったあとを考えると、gcd(a,b) のa,bはもともとの半分以下になっているはずです。

よって2回ごとに最悪でも半分になることを考えると、計算量は \(O(\log \min(a,b))\) になります。

C++ での実装例

※ gcd はC++17 から標準ライブラリに追加されています。以下は C++14 での例です。

long long gcd(long long a, long long b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

ユークリッドの互除法の気持ちと正当性

アルゴリズムを理解するために、具体例を見てから、数学的証明を与えます。

具体例

48, 32 の最大公約数を例として考えてみます。まずは素因数分解を用いて求めてみると、

$$ 48 = 2^4\times 3$$

$$ 32 = 2 ^5$$

となるので、最大公約数は 16 になります。

それではユークリッドの互除法を用いて求めてみましょう。

  1. gcd(48,32) = gcd(32, 48%32)
  2. gcd(32,16) = gcd(16, 32%16)
  3. gcd(16,0) = 16

これで 16 が求まりました。

数学的証明

以下の式が成り立つ事を示しましょう。

$$gcd(a,b) = gcd(b,a\%b)$$

これは、

$$gcd(a,b) \le gcd(b,a\%b)\tag{1}$$

$$ gcd(a,b) \ge gcd(b,a\%b) \tag{2}$$

の2つを証明することで示すことができます。

以下、\(a \ge b\)として考え、

$$ a = qb + r $$

のように表すことができるとします。(\(q\) は商、\(r\) は余りです)。

まず(1)を考えます。
\(a, b\) の任意の公約数を \(m\)とします。これが \(b, a%b\) の公約数でもあれば 、(1)の式が成立するはずです。

実際に、\(b\) は \(m\) の倍数で、

$$ a\%b = r = qb – a$$

から\(qb – a\) は \(m\) の倍数なので \(b%a\) も \(m\) の倍数です。

次に(2)を考えます。
(1)の逆で、\(b, a%b\) の任意の公約数を \(m\) とします。これが \(a, b\) の公約数でもあれば 、(2)の式が成立するはずです。

実際に、\(b\) は \(m\) の倍数で、

$$ a = qb +r $$

から、\(a\) も \(m\) の倍数です。

以上より示されました。

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

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

$$ ax+by=gcd(a,b)$$

の形をした、2変数の一次方程式の整数解を求めることができます。

練習問題