中国剩余定理(CRT)

定义：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：适用于所有模数两两间互质的情况

1. 计算所有模数的乘积$n=\prod_{i=1}^k n_i$

2. 对于第$i$个方程：

a. 计算$m_i=\frac{n}{n_i}$

b. 计算$m_i$在$mod\; n_i$意义下的逆元$m_i^{-1}$

c. 计算$c_i=m_im_i^{-1}$【此过程不能取余】

1. 得到唯一解：$x=\sum_{i=1}^k a_ic_i(mod\;n)$

x,y = 0,0
def exgcd(a, b):
    ......
n = int(input())
lis = []
A,ans = 1,0
for i in range(n):
    lis.append(tuple(map(int, input().split())))
    A *= lis[i][0]
for i in range(n):
    B = A // lis[i][0]
    exgcd(B, lis[i][0])
    ans += B * x * lis[i][1]  % B和B的逆元
ans = (ans % A + A) % A
print(ans)

法2：适用于更一般的情况，并且可以判断是否有解

通过两两合并方程的方式进行，下面讲合并两个方程的思路

有：$x\equiv a_1(mod\;m_1),x\equiv a_2(mod\;m_2)$

转换为等式形式：$x=m_1x+a_1=m_2y+a_2$

即：$m_1x-m_2y=a_2-a_1$

无解的条件判断：$(a_2-a_1)\;mod\;gcd(m_1,m_2)!=1$

若有解，则可以通过exgcd求解出一组解$(x_0,y_0)$

则合并后的方程为：$x\equiv(m_1x_0+a_1)\;(mod(lcm(m_1,m_2)))$

两个可以拓展至$N$个方程的方程组上去

x,y = 0,0
def exgcd(a, b):
    ......
n = int(input())
A,M,ok = 1,0,1
for i in range(n):
    a,m = map(int, input().split())
    d = exgcd(A, a)
    if (m - M) % d != 0:
        ok = 0
        break
    M = A * x * (m - M) // d + M
    A = A * a // d
if not ok: print(-1)
else: print((M % A + A) % A)