1.4.1. 最大公約数¶
Code: gcd_and_lcm.py
Test: test_gcd_and_lcm.py
最大公約数とは¶
Greatest common divisor (Wikipedea)
2つ以上の整数の公約数のうち、最も大きい数のことをいう。
例えば \(12, 18, 24\) の公約数は \(1, 2, 3, 6\) であり、最大公約数は \(6\) である。
法則¶
最大公約数は交換則と結合則が成り立つ。
交換則 \(\gcd(a, b) = \gcd(b, a)\)
結合則 \(\gcd(a, \gcd(b, c)) = \gcd(\gcd(a, b), c)\)
また、次の法則が成り立つ。これらはユークリッドの互除法の要である。
\(\gcd(a, 0) = a\)
\(\gcd(a, b) = \gcd(b, a \bmod b) \quad (a > b)\)
ユークリッドの互除法¶
ユークリッドの互除法は、2つの整数の最大公約数を求めるアルゴリズム。
自然数 \(a, b \quad (a > b)\) について \(\gcd(a, b) = \gcd(b, a \bmod b)\) が成り立つことを利用する。
常に \(a \geq b\) となるよう \(a, b\) を入れ替えつつ上式を再帰的に適用すると、剰余 \(r'\) が\(0\)になったときの除数 \(b'\) が最大公約数となる。
例えば、\(\gcd(12, 18)=6\) の導出過程は次の通り。
\[\begin{split}\begin{eqnarray}
\gcd(12, 18) &=& \gcd(18, 12) \\
&=& \gcd(12, 18 \bmod 12) = \gcd(12, 6) \\
&=& \gcd(6, 12 \bmod 6) = \gcd(6, 0) \\
&=& 6 \\
\end{eqnarray}\end{split}\]
上式では最初に交換則を適用したが、次式のように剰余をとることでも交換ができる。
これにより、 \(a, b\) の大小関係を考慮する必要がなくなる。
\[\gcd(12, 18) = \gcd(18, 12 \bmod 18) = \gcd(18, 12)\]
実装¶
概要¶
複数の整数の最大公約数を求める。
実装のポイント¶
Python3.8以下では math.gcd が2引数しかとれないため、3引数以上でも計算できるようにした。
計算量¶
gcd(a, b)\(\mathcal{O}(\log{\min(a, b)})\)
コード¶
[1]:
def gcd(a: int, *args: int) -> int:
for b in args:
while b > 0:
a, b = b, a % b
return a