2020-2021:teams:legal_string:jxm2001:同余最短路
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:同余最短路 [2021/09/04 20:54] jxm2001 [例题三] |
2020-2021:teams:legal_string:jxm2001:同余最短路 [2021/09/05 08:46] (当前版本) jxm2001 [例题三] |
||
|---|---|---|---|
| 行 163: | 行 163: | ||
| 预处理 $O(\sqrt k)$ 范围的数后对每个 $k$ 进行因式分解，时间复杂度 $O\left(\frac {\sqrt k}{\ln k}\right)$。 | 预处理 $O(\sqrt k)$ 范围的数后对每个 $k$ 进行因式分解，时间复杂度 $O\left(\frac {\sqrt k}{\ln k}\right)$。 | ||
| - | 如果 $k$ 是质数，只需要判定 $k\mid n$ 是否成立。如果 $k$ 有两种素因子，记为 $a,b$，于是等价于求解 $ax+by=n$ 的非负整数解。 | + | 如果 $k=1$，显然无解。如果 $k$ 是质数，只需要判定 $k\mid n$ 是否成立。 |
| + | |||
| + | 如果 $k$ 有两种素因子，记为 $a,b$，于是等价于求解 $ax+by=n$ 的非负整数解。 | ||
| 找到最小的 $y$ 满足 $y\equiv nb^{-1}\bmod x$，然后验证此时 $by$ 是否不超过 $n$ 即可。 | 找到最小的 $y$ 满足 $y\equiv nb^{-1}\bmod x$，然后验证此时 $by$ 是否不超过 $n$ 即可。 | ||
2020-2021/teams/legal_string/jxm2001/同余最短路.1630760060.txt.gz · 最后更改: 2021/09/04 20:54 由 jxm2001
