2020-2021:teams:legal_string:lgwza:扩展中国剩余定理
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:扩展中国剩余定理 [2021/01/21 11:39] lgwza |
2020-2021:teams:legal_string:lgwza:扩展中国剩余定理 [2021/01/21 11:53] (当前版本) lgwza |
||
|---|---|---|---|
| 行 18: | 行 18: | ||
| 不保证 $m_i$ 互质，保证有解 | 不保证 $m_i$ 互质，保证有解 | ||
| - | 代码： | + | **题解**： |
| + | |||
| + | 对于只有 $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$ 次扩展欧几里得算法，不断合并方程，直至得到最终解。注意过程中乘法要用快速乘避免溢出，注意取模时的模数是什么。 | ||
| + | |||
| + | **代码**： | ||
| <hidden> | <hidden> | ||
2020-2021/teams/legal_string/lgwza/扩展中国剩余定理.1611200382.txt.gz · 最后更改: 2021/01/21 11:39 由 lgwza
