#5 数据

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;
}