BSGS 相关笔记。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int qmi(int a, int k, int mod) {
    int res = 1 % mod;
    while (k) {
        if (k & 1) res = res * a % mod;
        a = a * a % mod, k >>= 1;
    }
    return res;
}

int a, b, p, T;
unordered_map<int, int> mp;

signed main() {
    scanf("%lld%lld%lld", &p, &a, &b), T = sqrt(p) + 1;
    for (int j = 0; j <= T; j++)
        if (qmi(a, j, p) == b) return printf("%lld\n", j), 0;
    for (int i = T; i >= 1; i--) mp[b * qmi(a, i, p) % p] = i;
    for (int j = 1; j <= T; j++) {
        int res = qmi(a, j * T, p) % p;
        if (mp.count(res)) return printf("%lld\n", j * T - mp[res]), 0;
    }
    puts("no solution");
    return 0;
}

快速幂多一个 $\log$ 可能会被卡，直接拿变量记就行了：

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a, b, p, T;
unordered_map<int, int> mp;

void BSGS() {
    T = sqrt(p) + 1, mp.clear();
    int mul = 1, now = 1;
    for (int i = 0; i <= T; i++) {
        if (mul == b) return printf("%lld\n", i), void();
        if (!mp.count(b * mul % p)) mp[b * mul % p] = i;
        if (i < T) mul = mul * a % p;
    }
    for (int j = 1; j <= T; j++) {
        now = now * mul % p;
        if (mp.count(now)) return printf("%lld\n", j * T - mp[now]), void();
    }
    puts("no solution");
}

signed main() {
    scanf("%lld%lld%lld", &p, &a, &b);
    BSGS();
    return 0;
}