Luogu P5605 小A与两位神仙

题意：给定模数 $m$ 和 $T$ 次询问，每次询问给定 $x, y$，问是否 $z$ 满足存在 $x ^ z\equiv y\pmod m$。$m\leq 10 ^ {18}, T\leq 2\times 10 ^ 4$，保证 $m$ 是奇质数的次幂，$\gcd(x, m) = \gcd(y, m) = 1$，3s。

首先考虑如何判断。仍然使用原根，令 $x = g ^ a$，$y = g ^ b$，那么就是问是否存在 $z$ 满足 $az\equiv b\pmod {\varphi(m)}$。那么显然合法的条件是 $b\bmod \gcd(a, \varphi(m)) = 0$。这样你就可以在单次 $O(\sqrt m)$ 的时间（？）求出，容易发现显然寄了。

注意到我们其实并不需要知道 $a, b$，我们其实只需要知道 $\gcd(a, \varphi(m))$ 和 $\gcd(b, \varphi(m))$ 即可。这个和什么有关呢？注意到 $x ^ {\frac m{\gcd(a, \varphi(m))}}$ 一定是 1，而且是最小的循环节。这样就是阶啊！显然我们需要使得 $\gcd(b, \varphi(m)) \bmod \gcd(a, \varphi(m)) = 0$，那么就是 $\dfrac m{\gcd(a, \varphi(m))} \bmod \dfrac m{\gcd(b, \varphi(m))} = 0$，也就是 $y$ 的阶整除 $x$ 的阶即可，记作 $\text{ord}(y) | \text{ord}(x)$。

现在问题转化为求阶了。一个显然的办法是枚举所有因数，看是否满足条件。这之前需要我们算出 $\varphi(m)$ 和他的分解。这个都需要使用 Pollard-Rho 算法，单次求解还是问题不大。然后枚举所有因数，复杂度为 $O(T\omega(n)\log n)$（检验需要快速幂），无法通过。

注意到一个数满足 $x ^ a\equiv 1\pmod m$，那么 $a$ 的所有倍数都满足。我们就可以每次试除每一个质因数即可，时间复杂度 $O(T\log ^ 2 n)$，可以通过。

std::vector<LL> Pollard_Rho(LL n);

int main()
{
	LL m, T, p, ti = 0, tmp, x, y;
	std::cin >> m >> T;
	p = Pollard_Rho(m).front();
	tmp = m;
	while (tmp % p == 0) tmp /= p, ti ++;
	if (ti) pr.push_back({p, ti - 1});
	auto vec = Pollard_Rho(p - 1);
	tmp = p - 1;
	for (LL &x : vec)
	{
		int t = 0;
		while (tmp % x == 0) t ++, tmp /= x;
		pr.push_back({x, t});
	}
	auto getord = [&](LL x) {
		LL ans = m / p * (p - 1);
		for (auto [p, cnt] : pr)
		{
			int t = 0;
			while (t < cnt && qpow(x, ans / p, m) == 1) ++ t, ans /= p;
		}
		return ans;
	};
	while (T --) scanf("%lld %lld", &x, &y), puts(getord(x) % getord(y) ? "No" : "Yes");
	return 0;
}