【洛谷P2485】计算器

BSGS模板题

代码如下

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL fpow(LL a, LL b, LL c) {
    LL ret = 1 % c;
    for (; b; b >>= 1, a = a * a % c) {
        if (b & 1) {
            ret = ret * a % c;
        }
    }
    return ret;
}
LL bsgs(LL a, LL b, LL p) {
    b %= p;
    unordered_map<LL, LL> mp;
    LL t = (LL)sqrt(p) + 1;
    for (int i = 0; i < t; i++) {
        LL val = b * fpow(a, i, p) % p;
        mp[val] = i;
    }
    a = fpow(a, t, p);
    if (a == 0) return b == 0 ? 1 : -1;
    if (b == 0) return -1;
    if (b == 1) return 0;
    for (int i = 0; i <= t; i++) {
        LL val = fpow(a, i, p);
        LL j = mp.find(val) == mp.end() ? -1 : mp[val];
        if (j >= 0 && i * t - j >= 0) {
            return i * t - j;
        }
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T, opt;
    cin >> T >> opt;
    while (T--) {
        LL y, z, p;
        cin >> y >> z >> p;
        if (opt == 1) {
            cout << fpow(y, z, p) << endl;
        } else if (opt == 2) {
            if (y % p == 0) {
                cout << "Orz, I cannot find x!" << endl;
            } else {
                cout << z * fpow(y, p - 2, p) % p << endl;
            }
        } else {
            LL ret = bsgs(y, z, p);
            if (ret == -1) {
                cout << "Orz, I cannot find x!" << endl;
            } else {
                cout << ret << endl;
            }
        }
    }
    return 0;
}