This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Rin204/Library-Python
$R = [R_1, R_2, \ldots]$, $M = [M_1, M_2, \ldots]$
が与えられたときに, $x \% M_i = R_i$ を満たす x (なければ -1) と M の最小公倍数 を返します.
x, m = Garner(R, M)
def ext_gcd(a, b): """ return (x, y, gcd(a, b)) s.t. ax + by = gcd(a, b) """ if b == 0: return 1, 0, a else: y, x, g = ext_gcd(b, a % b) return x, y - (a // b) * x, g def Garner(R, M): r = 0 m = 1 for ri, mi in zip(R, M): if ri < 0 or mi <= ri: ri %= mi if m < mi: m, mi = mi, m r, ri = ri, r if m % mi == 0: if r % mi != ri: return -1, -1 continue im, _, g = ext_gcd(m, mi) if im < 0: im += mi if (ri - r) % g != 0: return -1, -1 ui = mi // g x = ((ri - r) // g % ui) * im % ui r += x * m m *= ui return r, m
Traceback (most recent call last): File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat bundled_code = language.bundle( ^^^^^^^^^^^^^^^^ File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle raise NotImplementedError NotImplementedError