最大公約数と最小公倍数
(NumberTheory/Basic/gcd_lcm.py)

• View this file on GitHub
• Last update: 2021-03-07 00:19:35+09:00

概要

最大公約数 (greatest common divisor, GCD) と最小公倍数 (east common multiple, lcm) を求めるアルゴリズム。

使い方

gcd(a: int, b: int) -> int
a と b の最大公約数を返す。計算量 $O(\log \min(a, b))$

lcm(a: int, b: int) -> int
a と b の最小公倍数を返す。計算量 $O(\log \min(a, b))$

all_gcd(array: Iterable[int]) -> int
array の全要素の最小公約数を返す。n = len(array)、a = min(array) とすると、計算量 $O(n + \log a)$

all_lcm_int(array: Iterable[int]) -> int
array の全要素の最大公倍数を返す。n = len(array)、a = array[0] * array[1] * ... * array[n - 1] とすると、計算量 $O(n + \log a)$

all_lcm_dict(array: Iterable[int]) -> Dict[int, int]
array 全要素の最大公倍数を (key, value) = (素因数, 素因数の個数) とした辞書で返す。n = len(array)、a = max(array) とすると、計算量 $O(n\sqrt a)$

Verified with

• TestCase/AOJ/ALDS1_1_B.test.py
• TestCase/AOJ/NTL_1_C.test.py

Code

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return (a * b) // gcd(a, b)


def all_gcd(array):
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


def all_lcm_int(array):
    ans = array[0]
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
    return ans


def all_lcm_dict(array):
    primes = {}
    for num in array:
        for k in range(2, int(num ** 0.5) + 1):
            cnt = 0
            while num % k == 0:
                cnt += 1
                num //= k
            if cnt != 0:
                if k not in primes:
                    primes[k] = cnt
                else:
                    primes[k] = max(cnt, primes[k])
        if num != 1:
            if num not in primes:
                primes[num] = 1
    return primes

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page