WA on #5 $\sim$ #11

根据这篇帖子，我猜测是我的扩欧写错了，但是看来看去好像都没有问题，求助 qwq

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<cmath>
using namespace std;
#define LL long long

LL quickpow(int a, int x, int mod)
{
	LL sum = 1, cnt = a;
	while(x)
	{
		if(x & 1)
			sum = (sum * cnt) % mod;
		cnt = (cnt * cnt) % mod;
		x >>= 1;
	}
	return sum;
}

int gcd(int a, int b)
{
	return (b == 0? a : gcd(b, a%b) );
}

int exgcd(int a, int b, int &x, int &y)
{
	if(b == 0)
	{
		x = 1, y = 0;
		return a;
	}
	
	int x1, y1, d;
	d = exgcd(b, a%b, x1, y1);
	x = y1, y = x1 - a/b*y1;
	return d;
}

int exBSGS(int a, int b, int p)
{
	a %= p, b %= p;
	if(b == 1 || p == 1)
		return 0;
	
	int A = 1, d, k = 0;
	
	while(1)
	{
		d = gcd(a, p);
		if(d == 1)
			break;
		if(b % d > 0)
			return -1;
		k ++, b /= d, p /= d;
		A = (A * (a / d)) % p;
		if(A == b)
			return k;
	}
	
	unordered_map <LL, LL> hash;
	LL am = 1, am_ = 1, tot = b;
	int m = ceil(sqrt(p));
	
	for(int j = 0; j < m; j ++)
		hash[tot] = j, tot = (tot * a) % p;
	
	for(int i = 1; i <= m; i ++)
		am_ = (am_ * a) % p;
	
	for(int i = 1; i <= m; i ++)
	{
		am = (am * am_) % p;
		if(hash.count(am))
			return i*m - hash[am] + k;
	}
	return -1;
}

int main()
{
	int T, K;
	int y, z, p;
	
	cin >> T >> K;
	for(int i = 1; i <= T; i ++)
	{
		cin >> y >> z >> p;
		if(K == 1)
			cout << quickpow(y, z, p) << '\n';
		if(K == 2)
		{
//			if(y % p == 0)
//			{
//				if(z % p == 0)
//					cout << "0\n";
//				else
//					cout << "Orz, I cannot find x!\n";
//				continue;
//			}
			int m, n, d = exgcd(y, p, m, n);
			if(z % d != 0)
				cout << "Orz, I cannot find x!\n";
			else
				cout << ( (m * z / d) % p + p ) % p << '\n';
		}
		if(K == 3)
		{
			int res = exBSGS(y, z, p);
			if(res == -1)
				cout << "Orz, I cannot find x!\n";
			else
				cout << res << '\n';
		}
	}
	return 0;
}