Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
def egcd(a, b):
"""
References: https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
"""
x, y, u, v = 0, 1, 1, 0
while a != 0:
q, r = b // a, b % a
m, n = x - u * q, y - v * q
b, a, x, y, u, v = a, r, u, v, m, n
gcd = b
return gcd, x, y
def gcd(*numbers):
"""
Reference: https://gist.github.com/endolith/114336
"""
from fractions import gcd
return reduce(gcd, numbers)
def lcm(numbers):
"""
Reference: https://gist.github.com/endolith/114336
"""
def lcm(a, b):
return (a * b) // gcd(a, b)
return reduce(lcm, numbers, 1)
def generalized_crt(ak, nk):
"""
ak : Parameter, [a1, a2, ..., ak]
nk : Parameter, [n1, n2, ..., nk]
should be len(ak) == len(nk)
"""
assert len(ak) == len(nk)
N = reduce(lambda x, y: x * y, nk, 1)
l = lcm(nk)
s = 0
for n, a in zip(nk, ak):
m = N / n
g, x, y = egcd(m, n)
s += (m / g) * x * a
s %= l
return s
if __name__ == "__main__":
x = 545
a1, n1 = 101, 111
a2, n2 = 6, 77
a3, n3 = 35, 85
print generalized_crt([a1, a2, a3], [n1, n2, n3]), x
@elliptic-shiho

This comment has been minimized.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.