$\text{BSGS}$ 用于解决高次同余方程的最小整数解，主要思想是分块。
引入
求出下面方程的最小非负整数解 $x$：
$$ a^x\equiv b\pmod p\quad (\gcd(a,p)=1) $$
此处的未知数 $x$ 在指数上，我们就要用到 $\text{BSGS}$（大步小步法，即 $\text{Baby Step Giant Step}$）算法。
思想
$\text{BSGS}$ 的本质是分块的思想，我们设 $m=\left\lceil\sqrt p\right\rceil$（注意是上取整），又设 $x=i\times m-j$，其中 $0\le i\le m,0\le j < m$；我们可以将原方程转化为：
$$ a^{i\times m-j}\equiv b\pmod p $$
在 $x=i\times m-j$ 中，$i$ 即为大步，$j$ 即为小步；我们将 $j$ 移到方程的右边得到：
$$ a^{i\times m}\equiv b\times a^j\pmod p $$
观察到 $j$ 只有 $\mathcal O(m)$ 种取值，所以我们对于每个 $j$，把 $b\times a^j\bmod p$ 的值记录下来，存放在哈希表中（有没有一种分块打表的感觉？）。然后枚举左半边的 $i$，将对应的值在哈希表中查找对应的 $j$，如果能找到对应的 $j$ 那么说明已经找到答案了。
对于插入哈希表中的 $j$ 的值，显然在同一个值时，$j$ 的值越大越好，那么直接覆盖即可，无需关注细节问题！
注意：代码中必须要判断无解情况！（本来就无解，或者没有找到合法解）
时间复杂度：$\mathcal O(\sqrt p)$
代码
int BSGS(int a, int b, int P) {
if (b % gcd(a, P)) return -1;
a %= P, b %= P, mp.clear();
int m = ceil(sqrt(P));
for (int i = 0; i <= m; i++, b = 1LL * b * a % P) mp[b] = i;
a = pow(a, m, p);
for (int i = 0, j = 1; i <= m; i++, j = 1LL * j * a % P) {
if (mp.count(j) && i * m >= mp[j]) return i * m - mp[j];
}
return -1;
}