中国剩余定理 CRT

若在序列 ${n_{i}}$ 中任意两个互质，求方程组

{\begin{cases} x \equiv a_{1} & (\mod n_{1}) \\ x \equiv a_{2} & (\mod n_{2}) \\ ⋮ \\ x \equiv a_{k} & (\mod n_{k}) \end{cases}

的解。注意到，对于第 $i$ 个方程，我们可以构造数

m_{i} = \frac{1}{n_{i}} \prod_{j = 1}^{k} n_{j}

再求 $m_{i}$ 对 $n_{i}$ 逆元，则此式具有性质

(m_{i} m_{i}^{- 1}) mod n_{j} = {\begin{cases} 1, & j = i \\ 0, & j \neq i \end{cases}

这说明每一个解都不影响其他方程，可以独立求解再求和。因此有

a_{i} m_{i} m_{i}^{- 1} \equiv a_{i} (\mod n_{i})

对所有的解累加求和得到方程组的解

x \equiv \sum_{i = 1}^{k} a_{i} m_{i} m_{i}^{- 1} (\mod \prod_{j = 1}^{k} n_{j})

cpp

ll crt(const vector<ll> &aa, const vector<ll> &nn) {
    ll prod = 1, ret = 0, n = aa.size();
    for (auto ni : nn)
        prod *= ni;
    for (int i = 0; i < n; i++) {
        ll m = prod / nn[i];
        ret += aa[i] * m * inv(m, nn[i]);
        ret %= prod;
    }
    return ret;
}

ll crt(const vector<ll> &aa, const vector<ll> &nn) {
    ll prod = 1, ret = 0, n = aa.size();
    for (auto ni : nn)
        prod *= ni;
    for (int i = 0; i < n; i++) {
        ll m = prod / nn[i];
        ret += aa[i] * m * inv(m, nn[i]);
        ret %= prod;
    }
    return ret;
}

练习

P1495 【模板】中国剩余定理(CRT)/曹冲养猪

中国剩余定理 CRT ​

练习 ​

中国剩余定理 CRT

练习