cpl/math/ext_gcd.py

View this file on GitHub
Last update: 1970-01-01 00:00:00+00:00

Code

from typing import Tuple


def ext_gcd(a: int, b: int) -> Tuple[int, int, int]:
    """Extended euclidean algorithm
    Solves `ax + by = gcd(a, b)`.

    Args:
        a: Integer1.
        b: Integer2.

    Returns:
        Tuple of gcd, x and y (the coefficients of Bezout's identity).

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

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.9.2/x64/lib/python3.9/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.9.2/x64/lib/python3.9/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError