最大公約数 (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

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

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