def gf_crt(U, M, K=None):
 p = prod(M, start=K.one)
 v = K.zero
 for (u, m) in zip(U, M):
  e = (p // m)
  (s, _, _) = K.gcdex(e, m)
  v += (e * ((u * s) % m))
 return (v % p)

def gf_crt ( U , M , K = None ) : p = prod ( M , start = K . one ) v = K . zero for ( u , m ) in zip ( U , M ) : e = ( p // m ) ( s , _ , _ ) = K . gcdex ( e , m ) v += ( e * ( ( u * s ) % m ) ) return ( v % p )
chinese remainder theorem .