25 lines
462 B
Python
25 lines
462 B
Python
"""Extended Euclidean algorithm.
|
|
|
|
egcd(a, b) returns (g, x, y) such that a*x + b*y == g == gcd(a, b).
|
|
Works for negative inputs and zero.
|
|
"""
|
|
|
|
def egcd(a, b):
|
|
if b == 0:
|
|
if a < 0:
|
|
return (-a, -1, 0)
|
|
return (a, 1, 0)
|
|
g, x1, y1 = egcd(b, a % b)
|
|
q = a // b
|
|
return (g, y1, x1 - q * y1)
|
|
|
|
|
|
def gcd(a, b):
|
|
return egcd(a, b)[0]
|
|
|
|
|
|
def lcm(a, b):
|
|
if a == 0 or b == 0:
|
|
return 0
|
|
return abs(a // gcd(a, b) * b)
|