$\Theta(n)$ 递推，请
by NaCly_Fish @ 2020-02-21 20:30:45
@[NaCly_Fish](/user/115864)
证明看不懂QWQ
by NXYorz @ 2020-02-21 20:33:13
@[NaCly_Fish](/user/115864)
请问扩欧的复杂度是多少
by NXYorz @ 2020-02-21 20:34:05
@[NXYorz](/user/232191) 单次 $O(\log{n})$
by zhanghengrui @ 2020-02-21 20:37:56
@[NXYorz](/user/232191) 这个题卡了高于 $\Theta(n)$ 的算法
by zhanghengrui @ 2020-02-21 20:38:50
请问
$k*i+r\equiv0\quad (mod\quad p)$
同时乘以$i^{-1},r^{-1}$
是怎么推出
$k*r^{-1}+i^{-1}\equiv0\quad (mod\quad p)$
的
by NXYorz @ 2020-02-21 21:15:11
@[NXYorz](/user/232191) ?
by andyli @ 2020-02-21 21:24:44
@[NXYorz](/user/232191)
$k*i+r\equiv 0$
$k+r*i^{-1}\equiv 0$
$k*r^{-1}+i^{-1}\equiv 0$
by Belarus @ 2020-02-21 21:24:47
@[NXYorz](/user/232191)
$k*i*i^{-1}*r^{-1}+r*i^{-1}*r^{-1}\equiv 0$
而 $i*i^{-1}\equiv 1$，$r*r^{-1}\equiv 1$
所以 $k*r^{-1}+i^{-1}\equiv 0$。
by Mr_Wu @ 2020-02-21 21:29:22
最后推出来的式子是
$i^{-1}\equiv\left\lfloor\dfrac{p}{i}\right\rfloor*(p\quad mod\quad i)^{-1}\quad (mod\quad p)$
为什么代码实现是这样呢
```cpp
inv[1] = 1;
for(int i = 2; i < p; ++ i)
inv[i] = (p - p / i) * inv[p % i] % p;
```
为什么是$(p - p\quad /\quad i)$
(大雾
by NXYorz @ 2020-02-21 21:40:36