BSGS算法c++实现

BSGS算法（Baby Step Giant Step算法）是用于解决离散对数问题的一种算法，其时间复杂度为O(sqrt(n))。以下是C++实现代码：

#include <iostream>
#include <unordered_map>
#include <cmath>

using namespace std;

typedef long long ll;

const ll MOD = 998244353;
unordered_map<ll, ll> mp;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return res;
}

ll BSGS(ll a, ll b, ll n) {
    ll m = ceil(sqrt(n));
    mp.clear();
    ll am = 1;
    for (ll i = 1; i <= m; ++i) {
        am = am * a % n;
        mp[am * b % n] = i;
    }
    ll t = qpow(a, m);
    am = 1;
    for (ll i = 1; i <= m; ++i) {
        am = am * t % n;
        if (mp[am]) return (i * m - mp[am] + n) % n;
    }
    return -1;
}

int main() {
    ll a, b, n;
    cin >> a >> b >> n;
    ll res = BSGS(a, b, n);
    if (res == -1) cout << "No Solution\n";
    else cout << res << endl;
    return 0;
}

其中，`mp`用于存储Baby Step的结果，`qpow`用于快速幂运算。`BSGS`函数中，首先计算Baby Step `am`，然后将其乘以$b$并对$n$取模，将结果存入`mp`中，然后计算Giant Step $t$，并将其乘以$am$，再次对$n$取模，如果在`mp`中找到了相同的值，则说明找到了离散对数，返回结果即可。