book
归档: OI 
flag
mode_edit

定理

设正整数 $m_1,m_2,⋯,m_n$ 两两互质,则同余方程组

$$ \begin{cases} x\equiv a_1(\mod m_1)&(1)\
x\equiv a_2(\mod m_2)&(2)\
\cdots\
x\equiv a_n(\mod m_n)&(n)\
\end{cases} $$

有整数解,且在模$M=\prod_{i=1}^n m_i$下解唯一。为:

$$ x=\sum_{i=1}^n a_iM_iM_i^{-1},M_i=M/m_i,M_i^{-1}(\mod m_i) $$

如果要求所有解,就再加$k$个$M$

说白了就是个求线性同余方程组的解,另外,这个算法有一个很中二的名字:大衍求一术

证明

首先考察乘积$a_iM_iM_i^{-1}$,在模$m_i$意义下的的值:

$$ a_iM_iM_i^{-1}\equiv a_i\times1\equiv a_i(\mod m_i) $$

如果模数不为$m_i$时,即为$m_j,j\not=i$由于$m_j$必定是$M_i$的约数,所以有:

$$ \forall j\in{1,2,\cdots ,n},j\not=i, \exists a_iM_iM_i^{-1}\equiv 0(\mod m_j) $$

所以我们考察上一节的公式,可以把公式拆成两部分:

$$ x=a_iM_iM_i^{-1}+\sum_{j\not=i}a_jM_jM_j^{-1} $$

注意到在模$m_i$意义下时,可以对公式进行变形:

$$ x=a_iMiM_i^{-1}+\sum{j\not=i}a_jM_jMj^{-1}\equiv a_i+\sum{j\not=i}0\equiv a_i(\mod m_i) $$

这样一来,$x$便是方程$(1)$的一个解,同理可得,$x$也是该方程组的一个解

代码

今天又看了一遍,觉得有点不对,少了代码qwq

template <typename T>
void exgcd(T a, T b, T &g, T &x, T &y) // ax + by = gcd(a, b) = g
{
    !b ? (x = 1, y = 0, g = a) : (exgcd(b, a % b, g, y, x), y -= (a / b) * x);
}
template <typename T>
T inv(T a, T m) //a^{-1} (\mod m)
{
    T gcd, x, y;
    exgcd(a, m, gcd, x, y);
    if (gcd == 1)
        return ((x % m) + m) % m;
    else 
        return -1;
}
template <typename T>
T crt(T *m, T *a, T n)
{
    T ans = 0, mi, M = 1;
    for (int i = 1; i <= n; ++i) M *= m[i];
    for (int i = 1; i <= n; ++i)
        mi = M / m[i], ans = (ans + a[i] * inv(mi, m[i]) * mi) % M;
    return ans < 0 ? ans + M : ans % M;
}

参考链接