• 原题链接
• 为什么 BSGS 的计算 $(A^B)^L,0\le L\le B,B=\sqrt p$ 的代码要逆序枚举呢？也就是以下代码的 $6$ 到 $8$ 行。

inline int BSGS(int a, int b, int p) {
    a %= p, b %= p;
    if (b == 1 || a == b) return b != 1;
    map<int, int> mp;
    int B = ceil(sqrt(p)), res = inf;
    for (int i = B; i; i--) {
        mp[ksmi(a, i * B, p)] = i * B;
    }
    for (int i = 0; i <= B; i++) {
        if (mp.find(b * ksmi(a, i, p) % p) != mp.end()) {
            res = min(res, mp[b * ksmi(a, i, p) % p] - i);
        }
    }
    if (res == inf) {
        return -1;
    } else {
        return res;
    }
}