题目链接 AcWing 224.计算器

为什么我这个代码会出错？

错误的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qmi(ll a, ll b, ll p) {
    ll ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ans = ans * a % p;
        }
        a = a * a % p;
    }
    return ans;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}
ll bsgs(ll a, ll b, ll p) {
    map<ll, ll> mp;
    ll t = sqrt(p) + 1, k = 1, m;
    for (ll B = 1; B <= t; ++B) {
        k = k * a % p;
        mp[b*k%p] = B;
    }
    m = k;
    for (ll A = 1; A <= t; ++A) {
        if (mp[m]) {
            return (A * t - mp[m]) % p;
        }
        m = m * k % p;
    }
    return -1;
}
int main() {
    ll t, k, y, z, p;
    cin >> t >> k;
    for (int i = 0; i < t; ++i) {
        cin >> y >> z >> p;
        if (k == 1) {
            cout << qmi(y, z, p) << endl;
        } else if (k == 2) {
            ll x, m;
            if (z % exgcd(y, p, x, m)) {
                cout << "Orz, I cannot find x!" << endl;
            } else {
                while (x < 0) {
                    x += p;
                }
            }
        } else {
            ll k = bsgs(y, z, p) % p;
            if (k == -1) {
                cout << "Orz, I cannot find x!" << endl;
            } else {
                cout << k << endl;
            }
        }
    }
    return 0;
}

出错用例：

8 3
729747280 945350145 692576509
1003782582 1052995490 874047913
830933225 1064553781 799657219
838858074 226936475 794398013
81849408 363441763 937530961
537548626 762299815 268774313
434803981 112377358 720989147
535017411 188743780 959592839

我的输出：

Orz, I cannot find x!
660548660
Orz, I cannot find x!
101265586
61062441
0
439374774
721409727

正确答案：

Orz, I cannot find x!
660548660
Orz, I cannot find x!
101265586
61062441
Orz, I cannot find x!
439374774
721409727

为什么会WA？求大佬指导。

提问于8天前

球场鸡王

2356