GMOJ S3909 【Idiot 的乘幂】

Description

求下列同余方程组的解 $x(1 \leq x < p)$ ，有 $T$ 组数据：

$$\left\{ \begin{aligned} x ^ a & \equiv b \pmod{p} \\ x ^ c & \equiv d \pmod{p} \\ \end{aligned} \right.$$ $$\gcd(a, c) = \gcd(b, p) = \gcd(d, p) = 1$$

若无解则输出 No Solution! 。

$$1 \leq T \leq 1.5 \times 10^5, 1 \leq p \leq 10^9, 1 \leq a, b, c, d \leq p$$

Solution

考虑从 $\gcd(a, c) = 1$ 入手。

发现方程的解 $x = x^1 = x^{(ak_1 + ck_2 = 1)} = x^{(ak_1 + ck_2 = \gcd(a, c))} = b^{k_1}d^{k_2}$ 。

用 $exgcd$ 求解出 $k_1$ 和 $k_2$ ，然后就可以求出 $x$ 了（ $x=b^{k_1}d^{k_2}$ ）。

当 $k_1$ 或 $k_2$ 为负数的时候要记得求 $b$ 和 $d$ 的逆元。

因为不保证 $p$ 为素数，所以不能够用费马小定理来求逆元。

因此要用 $exgcd$ 或欧拉函数来求逆元。

最后记得要将得到的解带入题目中给出的方程检验判断是否无解。

时间复杂度 $O(T \log p)$ 。

Code

#include <cstdio>
long long p = 0;
long long pow (long long x, long long y)
{
	if(y == 0)
	{
		return 1;
	}
	else
	{
		long long dq = pow(x, y >> 1);
		if(!(y & 1))
		{
			return dq * dq % p;
		}
		else
		{
			return dq * dq % p * x % p;
		}
	}
}
void exgcd (long long a, long long b, long long &x, long long &y)
{
	if(b == 0)
	{
		x = 1, y = 0;
		return ;
	}
	exgcd(b, a % b, x, y);
	long long xx = y;
	long long yy = x - (a / b) * y;
	x = xx, y = yy;
}
int main ()
{
	long long T = 0;
	scanf("%lld", &T);
	while(T--)
	{
		long long a = 0, b = 0, c = 0, d = 0, x = 0, y = 0;
		scanf("%lld %lld %lld %lld %lld", &a, &b, &c, &d, &p);
		exgcd(a, c, x, y);
		long long ans = 1;
		long long bb = b, dd = d;
		if(x < 0)
		{
			x = -x;
			long long X = 0, Y = 0;
			exgcd(b, p, X, Y);
			bb = (X + p) % p;
		}
		if(y < 0)
		{
			y = -y;
			long long X = 0, Y = 0;
			exgcd(d, p, X, Y);
			dd = (X + p) % p;
		}
		ans = pow(bb, x) * pow(dd, y) % p;
		if(pow(ans, a) == b && pow(ans, c) == d)
		{
			printf("%lld\n", ans);
		}
		else
		{
			printf("No Solution!\n", ans);
		}
	}
	return 0;
}