@[KCID](/user/112651) 不太对吧，对于不互质的情况，根据鸽巢原理，$p$ 个数模 $p$ 意义下一定有两个相同的数，此时也会出现循环节。
by max67 @ 2021-11-04 21:49:11
@[houzhiyuan](/user/98490) 主要是逆元不一定存在的问题
by Wu_Ren @ 2021-11-04 21:50:56
@[Wu_Ren](/user/76039) 那如果先用 $exbsgs$ 判断有没有解再跑普通的 $bsgs$ 呢？
by max67 @ 2021-11-04 21:55:12
不是，没有逆元怎么BSGS？
by itisover @ 2021-11-04 21:57:00
@[max67](/user/223891)
一般而言，你是在hash表里加入 $a^{iB}$ 次方，然后用 $ba^j$ 去查，假设查到了，那么有：
$$a^{iB}\equiv ba^j\pmod p$$
假设逆元一定存在，那么才有
$$a^{iB-j}\equiv b\pmod p$$
但是 $\gcd(a,p)>1$ 时逆元不一定存在，所以不能这样认为
by Wu_Ren @ 2021-11-04 21:58:25
悟了，谢谢
by max67 @ 2021-11-05 07:02:10