def crt(a_list, m_list):
M = 1
for m in m_list:
M *= m
res =
for a, m in zip(a_list, m_list):
Mi = m
inv = pow(Mi, -1, m)
res += a * Mi * inv
return res
B
def crt(a_list, m_list):
M = 1
for m in m_list:
M *= m
res =
for a, m in zip(a_list, m_list):
Mi = M // m
inv = pow(Mi, -1, m)
res += a * Mi * inv
return res % M
C
def crt(a_list, m_list):
M = 1
for m in m_list:
M += m
res =
for a, m in zip(a_list, m_list):
Mi = M // m
inv = pow(Mi, m, -1)
res += a * Mi * inv
return res % M
D
def crt(a_list, m_list):
M = 1
for m in m_list:
M *= m
res =
for a, m in zip(a_list, m_list):
Mi = M // m
inv = pow(m, -1, Mi)
res += a * Mi * inv
return res