封面来源
Pixiv 夕燒-95681740
CRT学习笔记
一、What is CRT(Chinese Remainder Theory)
中国剩余定理,小学奥数好像就讲过,不用学了吧
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
—-《孙子算经》
根据这个问题,我们可以很快地写出一个暴力优雅的枚举
|
|
~~本文完。~~并没有
我们仔细观察一下这个问题,可以简化成一个一元线性同余方程组
$$ \left{ \begin{aligned} &x\equiv a_1\pmod {m_1}\ &x\equiv a_2\pmod{m_2}\ &…… \ &x\equiv a_t\pmod{m_t}\ \end{aligned} \right. $$
且$m_{1}$,$m_{2}$, $\cdots$,$m_{t}$两两互质。
它的解为
$$ 设M = m_{1} \times m_{2} \times m_{3} \times\cdots\times m_{t}= \prod_{i=1}^{t}m_{i} , $$
$$ M_{i}=M/m_{i},\forall i \in \lbrace1,2,…,n\rbrace , $$
$$ t_{i} = M_{i}^{-1},t_{i} 为 M_{i} 模 m_{i}意义下的逆元\ $$
$$ M_{i}t{i}\equiv 1\pmod{m_t},\forall i \in \lbrace1,2,…n\rbrace\ $$
$$ x = a_1t_1M_1+a_2t_2M_2+…+a_nt_nM_n+kM=kM+\sum^n_{i=1}a_it_iM_i,k \in Z\ $$
$$ 在模M的意义下只有一个解 \ $$
$$ x = (\sum_{i=1}^na_it_iM_i)\pmod{M}\ $$
二、CRT的应用
例题 P1495 【模板】中国剩余定理(CRT)/曹冲养猪
就是套公式
$$ 猪的总数\equiv无家可归的猪\pmod{猪圈数} $$
|
|
练习题
三、Reference
1.数论选讲(更新中)_zxyoi_dreamer的博客-CSDN博客
3.《孙子算经》