中国余剰定理

 1func crt(r []int, m []int) (int, int) {
 2	r0, m0 := 0, 1
 3
 4	invGcd := func(a, p int) (int, int) {
 5		x, u := 1, 0
 6		for p != 0 {
 7			t := a / p
 8			a, p = p, a-t*p
 9			x, u = u, x-t*u
10		}
11		return a, x
12	}
13
14	for i := 0; i < len(r); i++ {
15		r1, m1 := r[i], m[i]
16		if m0 < m1 {
17			r0, r1 = r1, r0
18			m0, m1 = m1, m0
19		}
20
21		if m0%m1 == 0 {
22			if r0%m1 != r1 {
23				return 0, 0
24			}
25			continue
26		}
27
28		g, im := invGcd(m0, m1)
29		if (r1-r0)%g != 0 {
30			return 0, 0
31		}
32
33		u := m1 / g
34		x := (r1 - r0) / g % u * im % u
35		r0 += m0 * x
36		m0 *= u
37	}
38
39	return (r0%m0 + m0) % m0, m0
40}
41