2020-2021:teams:legal_string:lgwza:扩展中国剩余定理
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:lgwza:扩展中国剩余定理 [2021/01/21 11:52] lgwza |
2020-2021:teams:legal_string:lgwza:扩展中国剩余定理 [2021/01/21 11:53] (当前版本) lgwza |
||
|---|---|---|---|
| 行 20: | 行 20: | ||
| **题解**： | **题解**： | ||
| - | 对于只有 $2$ 个方程的情况：$x\equiv a_1\pmod{m_1};x\equiv a_2\pmod{m_2}$，等价于 $x=a_1+m_1t_1=a_2+m_2t_2$，即 $m_1t_1-m_2t_2=a_2-a_1$，用扩展欧几里得解出 $t_1$，（若无解则方程组无解），从而得到 $x$ 的解 $x\equiv x_0\pmod{\text{lcm}(m_1,m_2)}$，从而将两个方程合并为一个。$n$ 个方程即执行 $n-1$ 次扩展欧几里得算法，不断合并方程，直至得到最终解。 | + | 对于只有 $2$ 个方程的情况：$x\equiv a_1\pmod{m_1};x\equiv a_2\pmod{m_2}$，等价于 $x=a_1+m_1t_1=a_2+m_2t_2$，即 $m_1t_1-m_2t_2=a_2-a_1$，用扩展欧几里得解出 $t_1$，（若无解则方程组无解），从而得到 $x$ 的解 $x\equiv x_0\pmod{\text{lcm}(m_1,m_2)}$，从而将两个方程合并为一个。$n$ 个方程即执行 $n-1$ 次扩展欧几里得算法，不断合并方程，直至得到最终解。注意过程中乘法要用快速乘避免溢出，注意取模时的模数是什么。 |
| **代码**： | **代码**： | ||
2020-2021/teams/legal_string/lgwza/扩展中国剩余定理.1611201156.txt.gz · 最后更改: 2021/01/21 11:52 由 lgwza
