Euclid
(byslib/numeric/euclid.py)

• View this file on GitHub
• Last update: 2022-04-19 13:16:57+09:00

Verified with

• tests/verify_pytest/test_numeric.test.py

Code

# @title Euclid
from typing import Tuple


def ext_gcd(a: int, b: int) -> Tuple[int, int, int]:
    """Extended Euclidean algorithm

    solve ax + by = gcd(a, b)

    Parameters
    ----------
    a
    b

    Returns
    -------
        (d, x, y) s.t. ax + by = gcd(a, b)
    """

    if b == 0:
        return a, 1, 0
    d, y, x = ext_gcd(b, a % b)
    return d, x, y - (a // b) * x


def crt(a: int, b: int, mod1: int, mod2: int) -> int:
    g, k, _ = ext_gcd(mod1, mod2)
    if (b - a) % g != 0:
        return -1
    k *= (b - a) // g
    ans = mod1 * k + a
    lcm = mod1 * mod2 // g
    return ans % lcm

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/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], 'release': True}).decode()
  File "/opt/hostedtoolcache/Python/3.10.4/x64/lib/python3.10/site-packages/onlinejudge_verify/languages/python.py", line 80, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page