中国剩余定理

题目 给定数组 \(a,m\)，保证所有 \(m\) 互质。请求出模方程组
\[ \begin{cases} x\equiv a_1 \mod m_1 \x\equiv a_2 \mod m_2 \\cdots \x\equiv a_n \mod m_n \\end{cases} \]
的最小正整数解。

分析 我们令 \(M=\prod_{i=1}^n m_i, w_i = \frac{M}{m_i}, p_i \equiv w_i^{-1} \mod m_i, e_i = w_i p_i\)，则有 \(x_0 = e_1a_1 + e_2a_2 + \cdots + e_na_n\) 是原方程组的一个解。这是因为 \(e_i \equiv w_ip_i \equiv 1 \mod m_i\)，而对于其它的 \(k\neq i\)，总有 \(e_k\equiv w_k\equiv 0 \mod m_i\)。也就是说，对于第 \(i\) 个方程，\(x_0\) 除了第 \(i\) 项为 \(a_i\) 外其他项均为 \(0\)（在模 \(m_i\) 意义下）。这便是中国剩余定理（Chinese Reminder Theorem）。代码如下：

ll crt(int n, ll *a, ll *m)
{
    ll M = 1, res = 0;
    for(int i = 1; i <= n; ++i)
        M *= m[i];
    
    for(int i = 1; i <= n; ++i) {
        ll w = M / m[i], p = inv(w, m[i]);
        res = (res + w * p * a[i]) % M;
    }
    return (res + M) % M;
}

中国剩余定理

原文：https://www.cnblogs.com/whx1003/p/11710890.html