概念

中国剩余定理(CRT)

对于线性同余方程组

$
\begin{cases}
x &\equiv a_1 \pmod {m_1} \\
x &\equiv a_2 \pmod {m_2} \\
&\vdots \\
x &\equiv a_n \pmod {m_n}
\end{cases}
$

其解为
$x \equiv x_0 \pmod {\text{lcm}(m_1, m_2, \cdots, m_n)}$

$x_0$为这个方程的任意一个解,其计算方法如下

对于第一和第二个方程

$
\begin{cases}
x &\equiv a_1 \pmod {m_1} \\
x &\equiv a_2 \pmod {m_2}
\end{cases}
$

其等价于方程组

$
\begin{cases}
x = a_1 + k_1p_1 \\
x = a_2 + k_2p_2
\end{cases}
$

消去x后得到
$a_1 + k_1m_1 = a_2 + k_2m_2$

令$g = gcd(m_1,m_2)$
若$g \mid (a_2 - a_1)$,则其存在整数解
即方程 $\frac{m_1}{g}k_1 - \frac{m_2}{g}k_2 = \frac{a_2 - a_1}{g}$

然后用扩展欧几里得解方程再回带就可解得$x_0$
共进行$n-1$次解出整个方程组

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
LL china(LL n,LL A[],LL M[])
{
LL a = M[0],c1 = A[0];
for(int i = 1;i < n;++i)
{
LL b = M[i],c2 = A[i];
LL x,y,d;
exgcd(a,b,d,x,y);
LL c = c2-c1;
if(c % d) return -1;
LL b1 = b/d;
x = ( (c/d*x)%b1 + b1)%b1;
c1 = a*x+c1;
a = a*b1;
}
if(c1 == 0) //当余数都为0,那么取最小公倍数
{
c1 = 1;
for(int i = 0;i < n;++i)
c1 = M[i]/gcd(c1,M[i])*c1;
}
return c1;
}

参考资料