数据

42148158 53237998 34885386

我的程序输出无解

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define pb push_back
#define se second
gp_hash_table<int, int> p;
int a, mod, b;
//map<int, int> p;
int power(int x, int y, int mod) {
    if (!y) return 1;
    int s = power(x, y / 2, mod);
    if (y & 1) return s * s % mod * x % mod; else return s * s % mod;
} 
int BSGS(int a, int b, int mod) {
    p.clear();
    if (b == 1) return 0;
    if (mod == 1) return 0;
    if (a == 0) {
        if (b == 1) return 0;
        if (b == 0) return 1;
        return -1;
    }
    const int len = sqrt(mod) + 1;
    int x = 1;
    for (int i = 0; i < len; i++) {
        p[b * x % mod] = i + 1; x = x * a % mod; 
    }
    int ssh = power(a, len, mod), now = 1;
    for (int i = 1; i <= mod / len; i++) {
        now = now * ssh % mod;
        int qwq = now;
        if (p[qwq] > 0) {
            return i * len - p[qwq] + 1;
        }
    } 
    for (int i = mod / len * len + 1; i <= mod; i++) {
        if (power(a, i, mod) == b) return i;
    }
    return -1;
}
int phi(int x) {
    int ans = x;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            ans = ans / i * (i - 1); 
            while (x % i == 0) x /= i;
        } 
    }
    if (x) {
        ans = ans / x * (x - 1);
    }
    return ans;
}
int inv(int a, int mod) {
    return power(a, phi(mod) - 1, mod);
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//  freopen("D:\\P4195_5.in", "r", stdin);
    int t = 0; 
    while (1) {
        t++;
        cin >> a >> mod >> b;
        if (!a && !mod && !b) break;
        a %= mod, b %= mod;
//      if (t == 80) {
//          cout << "data: " <<a<<" "<<mod<<" "<<b<<"\n";
//      }
        if (mod == 1 || b == 1) {
            cout << "0\n"; continue;
        }
        int gc = __gcd(a, mod);
        bool flag = 1;
        int dlt = 0, ans = -1;
        while (gc > 1 && a) {
            if (b == 1 || mod == 1) {
                ans = 0; break;
            }
            if (b % gc != 0) {
                flag = 0; break;
            }
            b /= gc; mod /= gc; dlt++; b = b * inv(a / gc, mod) % mod; gc = __gcd(a, mod);
        }
        if (ans != -1) cout << ans + dlt << "\n";
        else {
            a %= mod, b %= mod;
            int qwq = BSGS(a, b, mod);
//      if (t == 80) {
//          cout << "now: " <<a<<" "<<mod<<" "<<b<<"\n";
//      }
            if (qwq == -1 || !flag) cout << "No Solution\n"; else cout << qwq + dlt << "\n";
        }
    }

    return 0;
}