generalized_crt.py

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

http://elliptic-shiho.hatenablog.com/entry/2016/04/03/020117