cp_library/math/nt/chinese_remainder_theorem_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/math/nt/mod_inv_fn.py

Code

import cp_library.math.nt.__header__
from math import prod
from cp_library.math.nt.mod_inv_fn import mod_inv

def chinese_remainder_theorem(rems, mods):
    mod, a = prod(mods), 0
    for r,m in zip(rems, mods):
        N = mod_inv(M:=mod//m,m)
        a += r*M*N % mod
    return a % mod

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from math import prod

def mod_inv(x, mod):
    a,b,s,t = x, mod, 1, 0
    while b:
        a,b,s,t = b,a%b,t,s-a//b*t
    if a == 1: return s % mod
    raise ValueError(f"{x} is not invertible in mod {mod}")

def chinese_remainder_theorem(rems, mods):
    mod, a = prod(mods), 0
    for r,m in zip(rems, mods):
        N = mod_inv(M:=mod//m,m)
        a += r*M*N % mod
    return a % mod

Back to top page