大步小步算法（Baby Step, Giant Step算法）

大步小步算法可以用来求解高次同余方程问题。

问题

给定整数 $a, b, p$，其中 $a, p$ 互质，求一个非负整数 $x$，使得 $a^x\equiv b~(mod~p)$

BSGS 算法

因为 $a, p$ 互质，所以可以在模 $p$ 意义下执行关于 $a$ 的乘、除运算。

设 $x = i \* t - j$，其中 $t= \lceil \sqrt{p} \rceil, 0 \leq j \leq t - 1$，则方程变为 $a^{i\* t-j} \equiv b~(mod~p)$。即 $(a^t)^i\equiv b \* a^j~(mod~p)$

对于所有的 $j \in [0, t-1]$，把 $b \* a^j~mod~p$ 插入一个哈希表。

枚举 $i$ 所有可能的取值，即 $i \in [0, t]$，计算出 $(a^t)^i~mod~p$，在哈希表中查找是否存在对应的 $j$，更新答案即可。时间复杂度为 $O(\sqrt{p})$

以下代码实现了 BSGS 算法，计算高次同余方程 $a^x \equiv b~(mod~p)$ 的最小非负整数解，无解时返回 $-1$

int bsgs(int a, int b, int p)
{
    map<int, int> h;
    h.clear();

    b %= p;
    int t = (int)sqrt(p) + 1;
    for(int j = 0; j < t; j++)
    {
        int val = (long long)b * qmi(a, j, p) % p; //b * a^j
        h[val] = j;
    }

    a = qmi(a, t, p); //a^t
    if(!a) return !b ? 1 : -1;

    for(int i = 0; i <= t; i++)
    {
        int val = qmi(a, i, p); //(a^t)^i
        int j = h.find(val) == h.end() ? -1 : h[val];
        if(j >= 0 && i * t - j >= 0) return i * t - j;
    }
    return -1;
}