中国剩余定理
定义
CRT可以求解如下形式的一元线性同余方程组,其中$n_i$两两互质
$$
\cases{
x \equiv a_1(mod\;n_1)\\
x \equiv a_2(mod\;n_2)\\
…\\
x \equiv a_k(mod\;n_k)
}
$$
过程
1、计算所有模数的乘积$n=\prod_{i=1}^k n_i$
2、对于第$i$个方程:
-
计算$m_i=\frac{n}{n_i}$
-
计算$m_i$在$mod\; n_i$意义下的逆元$m_i^{-1}$
-
计算$c_i=m_im_i^{-1}$【此过程不能取余】
3、得到唯一解:$x=\sum_{i=1}^k a_ic_i(mod\;n)$
x,y = 0,0
def exgcd(a, b):
global x,y
if b == 0:
x,y = 1,0
return a
d = exgcd(b, a % b)
x,y = y,x
y -= a // b * x
return d
def CRT(k, a, m):
res = 0
N = 1
for i in range(k): N *= m[i]
for i in range(k):
t = N // m[i]
exgcd(t, m[i])
print(N, t, m[i], x, y)
res = (res + a[i] * t * x) % N
res = (res + N) % N
return res
print(CRT(3, [2, 3, 2], [3, 5, 7]))