发布时间：2025-06-03

光速幂

类似$BSGS$算法

假设需要很多次$v^x (\mod p)$的结果

可以预处理出$v^0,v^1,...,v^s,v^{2s},v^{ts(ts \lt p)}$

那么$x=as+b$就可以求出来

复杂度$O(\sqrt p)-O(1)$

以上方法适用于底数不变的情况

否则的话，找到$p$的原根(比如：$1e9+7$的原根是$5$，$998244353$的原根是$3$)

预处理每个需要算的值$g^x \equiv v(\mod p)$的$x$

那么假设需要算$v^b$就是算$g^{xb}$,转化为同底数