本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
中国剩余定理
是什么?
是一个关于同余方程的定理.
有啥用?
可以用来解一些同余方程组, 形如:
\[\left \{ \begin{array}{}
x \equiv a_1 \quad (\bmod n_1) \\
x \equiv a_2 \quad (\bmod n_2) \\
x \equiv a_3 \quad (\bmod n_3) \\
\cdots \\
x \equiv a_k \quad (\bmod n_k)
\end{array}\right.
\]
其中 \(n_1,\ n_2,\ n_3\ \dots\ n_k\) 两两互质.
若 \(n_1,\ n_2,\ n_3\ \dots\ n_k\) 不满足两两互质, 则需要ExCRT.
怎么搞?
- 计算所有
膜数的积, 记作 \(n\).
- 对于每个方程:
- 计算 \(\frac{n}{n_i}\), 记作 \(m_i\),
- 计算 \(m_i\) 在
膜 \(n_i\) 意义下的逆元, 记作 \(m^{-1}_i\),
- 计算 \(m_i \times m^{-1}_i\), 记作 \(c_i\), 注意不要对 \(c_i\) 取模.
暴力%不可取
- 得到方程组的唯一解:
\[x = \sum^k_{i=1} a_i \times c_i \quad (\bmod n)
\]
怎么证?
设 \(j \not= i\), 由于模数两两互质, 则 $m_j \equiv 0 \quad(\bmod n_i) $,
所以 \(c_j \equiv 0 \quad (\bmod n_i)\),
于是
$x \equiv \sum^k_{z=1} a_z \times c_z \equiv a_i \times c_i \equiv a_i \times m_i \times m_i^{-1} \equiv a_i \quad (\bmod n_i) $,
这样我们能够证明该算法的正确性.
若存在一个数 \(y\), 使 \(y \not= x\), 则一定存在 \(n_i\), 使 \(x \not\equiv y \quad (\bmod n_i)\),
所以求出的解 \(x\) 是唯一的.
怎么写?
Luogu P1495 曹冲养猪 (裸 CRT)
