P11961 的一个无脑做法

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T, n, d, P, qwq, x, y;
map<long, long> mp;
int exgcd(int a, int b, int &x, int &y){
	if (!b){
		x = 1, y = 0;
		return a;
	}
	int g = exgcd(b, a % b, x, y);
	swap(x, y);
	y -= a / b * x;
	return g;
}
int inv(int k, int p){
	exgcd(k, p, x, y);
	return (x % p + p) % p;
}
int qpow(int x, int k, int mod){
	int ans = 1;
	while (k){
		if (k & 1)
			ans = ans * x % mod;
		x = x * x % mod;
		k >>= 1;
	}
	return ans;
}
int bsgs(int a, int b, int p){
	mp.clear();
	int blo = ceil(sqrt(p)), tmp = b;
	for (int i = 0; i <= blo; i++){
		mp[tmp] = i;
		tmp = tmp * a % p;
	}
	int tx = qpow(a, blo, p);
	tmp = 1;
	for (int i = 1; i <= blo; i++){
		tmp = tmp * tx % p;
		if (mp[tmp])
			return i * blo - mp[tmp];
	}
	return -1;
}
int exbsgs(int a, int b, int p){
	//if (p == 1 || (b %= p) == 1)
	//	return 0;
	int g = __gcd(a, p), k = 0, prod = 1;
	while (g > 1){
		if (b % g > 0)
			return -1;
		k++;
		b /= g;
		p /= g;
		prod = prod * (a / g) % p;
		if (prod == b)
			return k;
		g = __gcd(a, p);
	}
	int res = bsgs(a, b * inv(prod, p) % p, p);
	return (res == -1 ? res : res + k);
}
vector<int> ans, di;
int gphi(int x){
	int tx = x, res = x;
	for (int i = 2; i * i <= tx; i++){
		if (tx % i == 0){
			res = res / i * (i - 1);
			while (tx % i == 0)
				tx /= i;
		}
	}
	if (tx > 1)
		res = res / tx * (tx - 1);
	return res;
}
bool pan(int x){
	if (x == 1 || x == 2 || x == 4)
		return 1;
	if (x % 2 == 0)
		x /= 2;
	vector<int> tmp;
	tmp.clear();
	if (x % 2 == 0)
		tmp.emplace_back(2);
	for (int i = 3; i * i <= x; i += 2){
		if (x % i == 0){
			if (tmp.size())
				return 0;
			tmp.emplace_back(i);
			while (x % i == 0)
				x /= i;
		}
	}
	if (x > 1 && tmp.size())
		return 0;
	return 1;
}
void work(int x){
	if (!(x & 1)){
		di.emplace_back(2);
		while (!(x & 1))
			x >>= 1;
	}
	for (int i = 3; i * i <= x; i += 2){
		if (x % i == 0){
			di.emplace_back(i);
			while (x % i == 0)
				x /= i;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> T;
	while (T--){
		cin >> d >> n;
		if (!pan(n)){
			cout << "0\n\n";
			continue;
		}
		P = gphi(n);
		ans.clear();
		di.clear();
		work(P);
		for (int i = 1; i <= n; i++){
			if (__gcd(i, n) != 1)
				continue;
			bool chk = 1;
			for (auto x : di)
				if (qpow(i, P / x, n) == 1){
					chk = 0;
					break;
				}
			if (chk){
				qwq = i;
				break;
			}
		}
		int awa = exbsgs(qwq, d, n);
	//	cerr << awa << "\n";
		if (awa == -1 || __gcd(awa, P) != 1)
			cout << "No\n";
		else
			cout << "Yes\n";
	}
	return 0;
}