快速幂写起来多舒服啊,为什么要写 exgcd 啊?
by Rui_R @ 2021-02-02 18:29:10
@[Rui_R](/user/101984) 因为我只会exgcd
by 滑蒻稽 @ 2021-02-02 18:30:17
理论上应该不会有问题啊,同时建议你把
``ll mod = 998244353`` 改成 ``const ll mod = 998244353``
by Rui_R @ 2021-02-02 18:30:18
@[Rui_R](/user/101984) 好的,可能不是逆元正负的问题导致我答案出错,我再调试一下
by 滑蒻稽 @ 2021-02-02 18:31:21
@[滑蒻稽](/user/113181) 很简单啊, $x$ 的逆元就是 ``fastpow(x,mod-2)``
by Rui_R @ 2021-02-02 18:31:21
@[Rui_R](/user/101984) 我先用着快速幂吧,等会再去看推导过程Orz
by 滑蒻稽 @ 2021-02-02 18:32:17
@[滑蒻稽](/user/113181)
~~您还可以用 O(1) 光速幂(~~
by Areka6219 @ 2021-02-02 18:36:43
@[滑蒻稽](/user/113181) 小费马就好了
by FxorG @ 2021-02-02 18:39:45
@[Rui_R](/user/101984) 知道了,,,,exgcd算出来的负数和1的最大公约数是-1,不满足同余方程$ax\equiv 1(mod\ m)$,自然得到的逆元就不对了....
by 滑蒻稽 @ 2021-02-02 19:24:18
困扰了我半天,甚至开了2个帖子
by 滑蒻稽 @ 2021-02-02 19:24:43