[tex]a^x \equiv b (\text{mod} p)[/tex]求最小的非负整数x。默认[tex]a \neq 0,p\geq 2[/tex]。

·bzoj3239模为质数(裸的BSGS)
若[tex]p|a[/tex]。[tex]b \equiv 0[/tex]时，[tex]x=1[/tex]；否则x无解。
否则a,p互质，由费马小定理，只需考虑[tex]x=0,1,\dots,p-2[/tex]。
取一个m，令[tex]x=mi-j[/tex]，[tex]i=1,2,\dots,m[/tex],[tex]j=1,2,\dots,m[/tex]。此时[tex]x=0,1,\dots,m^2-1[/tex]，所以只要取[tex]m^2\geq p-1[/tex]即可。
则[tex]a^{mi-j} \equiv b(\text{mod}p)[/tex]
等价于[tex]a^{mi} \equiv b\cdot a^j(\text{mod}p)[/tex]
等号两边分别遍历i和j，用hash表检查是否出现重复值，并保留最小解即可。

·bzoj2995模可能为合数
分解模[tex]p=\prod_{i=1}^k {p_i}^{d_i}[/tex]，等价转换为k个形如[tex]a^x \equiv b(\text{mod}p^d)[/tex]的方程。若其中任意一个无解，则原方程无解。
①[tex]p \nmid a[/tex]，则可以使用上述BSGS解出最小非负整数解[tex]x_0[/tex]。
再求[tex]a^x \equiv 1(\text{mod}p^d)[/tex]的最小正整数解K（即a对模p^d的阶)，可以用BSGS，也可以枚举[tex]\varphi(p^d)=p^d-p^{d-1}[/tex]的所有约数进行检查。
则所有形如[tex]x\equiv x_0(\text{mod}K)[/tex]的非负整数x均是此方程的解。
（当[tex]a\equiv 1(\text{mod}p^d)[/tex]时此方法仍然有效，其中求得的K=1）
②[tex]p|a[/tex]，且[tex]b\equiv 0 (\text{mod}p^d)[/tex]。
由于a中含有p的因子，那么在x充分大的时候一定能有[tex]a^x\equiv 0\equiv b(\text{mod}p^d[/tex]。
令[tex]a=p^qa'[/tex]，[tex]q\geq 1,p\nmid a'[/tex]，则[tex]x \geq x_0=\left \lceil d/q \right \rceil[/tex]均为此方程的解。
③[tex]p|a[/tex]，且[tex]b \not \equiv 0(\text{mod}p^d)[/tex]。
由上讨论，可知此时x不会超过[tex]d/q[/tex]，而这是一个很小的范围（在32以内）。所以若这种情况出现，只需对原方程暴力检验32以内的x后即可跳出。

假如不出现情况③，把①中得到的所有结果按中国剩余定理合并，并从中取满足②下界的最小x即为答案。

upd:后来学会了更加简单的消因子做法。。。稍微写一下吧

首先对x<=logp暴力。

现在假设x>logp,a^x=b (mod p)。

（边界：p=1，那么x就是任意非负整数）

设d=gcd(a,p)，若d=1，则a存在逆元，可以BSGS。

若d!=1，需要有d|b，于是写成d*a'*a^{x-1}=d*b' (mod d*p')，

即a'*a^{x-1}=b' (mod p')，由于gcd(a',p')=1，a'是存在逆元的，那么a^{x-1}=b'*a'^{-1} (mod p')，继续求出x-1就好。

每次p至少减半，所以x至多减logp次，因此要对logp以内暴力。