中国剩余定理

已知 $m_1,m_2\cdots m_k$ 互质，方程 $\left\{ \begin{array}{c} x\equiv a\_1\left( \mod m\_1 \right)\\ \begin{array}{l} x\equiv a\_2\left( \mod m\_2 \right)\\ \cdots\\ x\equiv a\_k\left( \mod m\_k \right)\\ \end{array}\\ \end{array} \right.$ 的最小正整数解 $x=a_1MM_1^{-1}+a_2MM_2^{-2}+\cdots a_kMM_k^{-k}$ ，其中 $M=m_1m_2\cdots m_k$ ， $M_i=\frac{M}{m_i}$ ， $M_i^{-1}$ 表示 $M_i$ 模 $m_i$ 的逆元，可通过 $M_ix\equiv1(\mod m_i)$ 求出

本质是求解同余方程组
如果直接按公式求解，结果可能会溢出，因此采用迭代的方式求解
$x\equiv a\left( \mathrm{mod} m \right) \Leftrightarrow x=mk+a,k\in \mathrm{Z}$
考虑第1个和第2个方程，可得等式 $m_1k_1+a_1=m_2k_2+a_2$ ，变形得 $m_1k_1-m_2k_2=a_2-a_1$
令 $d=\text{gcd}(m_1, -m_2)$ 方程有解的充分必要条件是 $d | (a_2-a_1)$
此时 $x=k_1m_1+a_1=(k_1+k\frac{m_2}{d})m_1+a_1=k_1m_1+k\frac{m_1m_2}{d}+a_1=k_1m_1+a_1+k\frac{m_1m_2}{d}=x_1+kd_{12}$ ，这里令 $x_1=k_1m_1+a_1$ ， $d_{12}=\frac{m_1m_2}{d}$
若把 $x_1$ 看成 $a_1$ ， $d_{12}$ 看成 $m_1$ ，则上式变成 $x=a_1+km_1$ ，即 $x\equiv a_1 (\mod m_1)$ ，相当于把两个同余方程合并成了一个

代码

typedef long long LL;

// 扩展欧几里得算法
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);      // 递归结束时，y = x'，x = y'
    y -= (a/b) * x;                    // y = x'-(a / b) * y' = y - (a / b) * x
    return d;
}

// 中国剩余定理
LL x = 0, m1, a1;
cin >> m1 >> a1;
for (int i = 0; i < n - 1; i ++ )
{
    LL m2, a2;
    cin >> m2 >> a2;
    LL k1, k2;
    LL d = exgcd(m1, -m2, k1, k2);      // 求的不是最终解k1和k2
    if ((a2 - a1) % d)
    {
        x = -1;
        break;      // 无解
    }

    k1 *= (a2 - a1) / d;                // 变换成真正的解
    int t = m2 / d;                     // k1 = k1 + k * m2 / d
    k1 = (k1 % t + t ) % t;             // 变换成最小的正整数（防止C++对负数模取余）

    x = k1 * m1 + a1;

    // 把两个方程合并成一个方程
    LL m = abs(m1 / d * m2);        // 变成正数
    a1 = k1 * m1 + a1;
    m1 = m;
}
if (x != -1) x = (x % m1 + m1) % m1;        // 变成最小正整数（防止C++对负数模取余）
cout << x << endl;

代码​

代码