最大公約数 ((拡張)ユークリッドの互除法)

最大公約数 (greatest common divisor, GCD)

概要

2つの数 \(a, b\) について、 \(a = a'g\), \(b = b'g\) (\(a', b'\) は互いに素)となるような \(g = gcd(a, b)\) を計算する。

拡張されたGCDでは、 \(ax + by = g\) となるような \(x, y, g\) を計算する。

また、最小公倍数(least common multiple, LCM)は \(\displaystyle \frac{ab}{gcd(a, b)}\) で計算する。

GCDはPythonの標準モジュールに含まれている。 (Python2であれば fractions.gcd(), Python3であれば fractions.gcd() もしくは math.gcd())

計算量

\(N = \max(a, b)\) とすると \(O(\log N)\)

実装

# Euclidean Algorithm
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

# Euclidean Algorithm (non-recursive)
def gcd2(m, n):
    while n:
        m, n = n, m % n
    return m

# Extended Euclidean Algorithm
def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a % b)
        y -= (a // b)*x
        return d, x, y
    return a, 1, 0

# lcm (least common multiple)
def lcm(m, n):
    return m//gcd(m, n)*n

戻る