按照正常的思路我们都直接将算法，但这会先讲一道题，然后再讲它的定义和求法。
参考：
背景
是一场ABC335里的G题，当时在赛场上大概留了一个多小时的时间，但一直都在想用BSGS，但显然最后没想出来。
而这题的瓶颈就在下面问题：
对于两个数 $a,b$，是否存在一个 $x$ 使得同余方程 $a^x \equiv b \pmod p$ 有解。
$a,b,p \leq 10^{13}$（原题数据范围）
大家看到的第一眼显然可以用BSGS求。
但这个算法是 $O(\sqrt p)$ 的（如果涉及到具体实现的话，可能还得乘个 $\log \sqrt p$，就是set、lower_bound查找的复杂度），比较适用于单组询问，很难推广应用。
所以还有另外一种方式，比较适用于多组询问。
是我们求出来 $a$ 和 $b$ 的阶，即 $\text{ord}_p a$ 和 $\text{ord}_p b$，看 $\text{ord}_p b$ 是否是 $\text{ord}_p a$ 的因子（$\text{ord}_p b \mid \text{ord}_p a$）即可。
这里先不证这个结论是否正确，但相信大家第一次看到“阶”的时候定然是一头雾水的，下面我就来说一下它的定义和求法。
定义
阶
阶的话，跟逆元相似，还是需要两个值，只不过这里叫做“$a$ 在模 $p$ 意义下的阶”而已，换汤不换料。
这个表示方法就是 $\text{ord}_p a$。
它的定义是：
- 给你整数 $a$、$p$。
- 找到最小的 $x$，使得同余方程 $a^x \equiv 1 \pmod p$ 成立。
- 这个 $x$，就是$a$ 在模 $p$ 意义下的阶。
原根
但说到阶，我们定要讲一下它的孪生兄弟，原根了。
原根的定义就是若 $\text{ord}_p a=\varphi(p)$，则称“$a$ 是 $p$ 的原根”。
性质
阶和原根的定义都很简单，接下来说一下它们的性质。
阶
首先，根据欧拉定理：
对于任意两个互质的数 $a$ 和 $p$，$a^x \equiv 1 \pmod p$ 方程必然有解 $x=\varphi(p)$。
在 $a$ 和 $p$ 互质的时候，阶显然存在。
但阶不一定是欧拉给出的解，但一定满足一个条件：
- $\text{ord}_p a$ 是 $\varphi(p)$ 的因子（$\text{ord}_p a \mid \varphi(p)$）。
根据阶的定义，我们还可以得到两个推论：
- $a^1,a^2,a^3, \dots a^{\text{ord}_p a}$ 在模 $p$ 意义下互不相等。
- $a^x \equiv a^y \pmod p \Leftrightarrow x \equiv y \pmod {\text{ord}_p a}$，充分必要条件。
还有很多的结论，具体可以看第二个参考文章。
原根
这里的性质认为不太会考，所以没写。
还是看第二个参考文章，里面也有证明。
求值
最后就是求值。
阶
由于 $\text{ord}_p a \mid \varphi(p)$，所以只要求出 $\varphi(p)$（多数时候 $p$ 都保证是质数，直接带 $p-1$ 即可），遍历其所有因子验证即可。
但这里也有个技巧，就是因子不用一个一个遍历，显然 $\text{ord}_p a$ 具有因子上的单调关系。
说一下，正常情况下二分等算法都是“值上的单调关系”，就是 $x$ 成立，$x+k$（$k \geq 0$）也一定成立。
而“倍数上的单调关系”意思是 $x$ 成立，那么 $xk$（$k \geq 1$）也成立。
这里的“因子上的单调关系”意思是 $x$ 成立，那么 $\dfrac{x}{k}$（$k \geq 1$）也成立。
所以只要做一下因式分解，然后从 $\varphi(p)$ 开始，将这些质因子一个一个尝试除以即可。
具体可以看参考文章，里面有代码。
另外，阶还有一个特性，就是种类特别少，其实也能理解，因为本来因子就少。
所以完全可以把所有的阶取出来后，去个重再计算。
原根
由于原根数量很多，分布均匀，所以直接暴力求即可。