ユークリッドの互除法
2つの整数の最大公約数を求める際、単純に素因数分解して、共通部分を求めようとすると時間がかかってしまいます。
このような時に、対数のオーダーで高速に最大公約数を求めるアルゴリズムとして、ユークリッドの互除法が古くから知られています。
Input: gcd(48,32)
Output: 16
アルゴリズム
ユークリッドの互除法 (gcd(a,b))：
- b が 0 ならば、a を返す
- 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 になります。
それではユークリッドの互除法を用いて求めてみましょう。
- gcd(48,32) = gcd(32, 48%32)
- gcd(32,16) = gcd(16, 32%16)
- 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変数の一次方程式の整数解を求めることができます。