Posts with tag 数论

中国剩余定理

题目：求 $x$ 满足以下，其中 $n_i$ 两两互质$$ cases(x mod n_1 = a_1, x mod n_2 = a_2, dots.v, x mod n_k = a_k) $$求解:计算模数的积 $n$对第 i 个方程令 $m_i = n / n_i$令 $m_i^(-1)$ 为 $m_i$ 在模 $n_i$ 下的逆元令 $c_i = m_i m_i^(-1)$，不要模 $n_i$模 $n$ 意义下 $x$ 唯一解为 $sum_(i = 1)^k a_i c_i$ . 正确性比较显