中國剩下的定理/kk
目錄
- 寫在前面
- 正文
- 中國剩餘定理公式：
- 中國剩餘定理拓展：
- 大數翻倍法
Q：中國剩餘定理很難嗎？
A：就是個求解同餘方程組的東東
(話說 \(OI\) 隻要能了解應用就好吧，證明是不是可以先放一放)因為我太菜了
Update 2021/04/11：終于了解中國剩餘定理，還是tcl
《孫子算經》中有這麼一道題：
“今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？”
翻譯一下就是：已知一個正整數模3餘2，模5餘3，模7餘2，求這個數是幾？
寫成數學語言，就是求解同餘方程組
\[\begin{aligned}
& x \equiv 2 \pmod 3 \\
& x \equiv 3 \pmod 5 \\
& x \equiv 5 \pmod 7 \\
\end{aligned}
\]
乍一看，這不很簡單蠻，随便帶近兩個數試試不就行了
但是你現在可以直接觀察并且資料小，如果資料大了呢，同餘方程組不隻是三個呢？
這就需要我們的“中國剩餘定理”登場了
設正整數 \(m_1, m_2, m_3, ···,m_k\) 兩兩互素，則同餘方程組
& x \equiv a_1 \pmod {m_1} \\
& x \equiv a_2 \pmod {m_2} \\
& x \equiv a_3 \pmod {m_3} \\
& ··· \\
& x \equiv a_k \pmod {m_k}
有整數解。并且在模 \(M = m_1 \times m_2 \times ··· \times m_k\) 下解是唯一的，解為
\[x \equiv (a_1 M_1 M_1^{-1} + a_2 M_2 M_2^{-1} + ··· + a_k M_k M_k^{-1}) mod \ \ M
其中 \(M_i = M / m_i\) ， 而 \(M_i^{-1}\) 為 \(M_i\) 模 \(m_i\) 的逆元
（求解模數不互質情況下的同餘方程組）
普通中國剩餘定理要求所有的 \(m_i\) 互素，那麼如果不互素呢？怎麼求解同餘方程組？
這種情況可以考慮兩兩合并，假設合并如下兩個方程：
\[x = a_1 + m_1 x_1
\[x = a_2 + m_2 x_2
那麼得到：
\[a_1 + m_1 x_1 = a_2 + m_2 x_2 \Rightarrow m_1 x_1 + m_2 x_2 = a_2 -
a_1\]
我們需要求出一個最小的 \(x\) 使它滿足：
\[x = a_1 + m_1 x_1 = a_2 + m_2 x_2
那麼 \(x_1\) 和 \(x_2\) 的值要僅可能的小，于是我們又擴充歐幾裡得算法求出 \(x_1\) 的最小整數解，将它代回 \(a_1 + m_1 x_1\) ，得到 \(x\) 的一個特解 \(x^{,}\) ，當然也是最小整數解。
是以 \(x\) 的通解一定是 \(x^{,}\) 加上 \(lcm(m_1,m_2) \times k\) 這樣才能保證 \(x\) 模 \(m_1\) 和 \(m_2\) 的餘數是 \(a_1\) 和 \(a_2\) 。由此，我們把這個 \(x^{,}\) 當做新的方程的餘數，把 \(lcm(m_1,m_2) \times k\) 當做新的方程的模數。（這一段是關鍵）
合并完成：
\[x \equiv x^{,} \pmod {lcm(m_1,m_2)}
複雜度有保證，碼量短小精湛！
詳見這篇博文
想學中國剩餘定理很久了，第一次聽說是在夏令營的時候，看到同宿舍某大佬的課程表上有這個名詞，感覺挺高大上的，前幾天忙着期中考咕咕咕了，如今終于有機會更一篇關于它的筆記了，開心>-<!