Fractional Power

$M=998244353$이라고 하자. $M$은 소수이므로, $M$으로 나누어떨어지지 않는 모든 정수는 법 $M$에서 역원을 가진다.

또한 페르마의 소정리에 의해, $a \not\equiv 0 \pmod M$이면

$$a^{M-1} \equiv 1 \pmod M$$

이다.

따라서 법 $M$에서 $0$이 아닌 수의 거듭제곱을 계산할 때, 지수는

$$\varphi = M-1 = 998244352$$

로 나눈 나머지만 중요하다.

문제의 조건에서

$$\gcd(|q|,\varphi)=1$$

이므로, $q$는 법 $\varphi$에서 역원을 가진다. 즉 어떤 정수 $r$이 존재하여

$$qr \equiv 1 \pmod \varphi$$

를 만족한다.

원래 식은

$$x^q \equiv n^p \pmod M$$

이다. 양변을 $r$제곱한다고 생각하면

$$(x^q)^r \equiv (n^p)^r \pmod M$$

이고,

$$x^{qr} \equiv n^{pr} \pmod M$$

이다. 그런데 $qr \equiv 1 \pmod \varphi$이므로, 페르마의 소정리에 의해

$$x^{qr} \equiv x \pmod M$$

이다. 따라서

$$x \equiv n^{pr} \pmod M$$

이다.

즉 가능한 $x$는 하나뿐이고, 정답은

$$n^{p q^{-1}} \pmod M$$

이다. 여기서 $q^{-1}$은 법 $M$에서의 역원이 아니라, 법 $M-1$에서의 역원이다.

알고리즘은 다음과 같다.

• $\varphi = 998244352$로 둔다.
• $p$를 법 $\varphi$에서 정규화하여 $P$를 구한다.
• $q$를 법 $\varphi$에서 정규화한 뒤, 확장 유클리드 알고리즘으로 역원 을 구한다.

주의할 점은 $998244352$가 소수가 아니라는 것이다. 따라서 $q^{-1} \pmod {998244352}$는 페르마의 소정리로 구하면 안 되고, 확장 유클리드 알고리즘으로 구해야 한다.

또한 $p,q$가 음수일 수 있으므로, 나머지를 계산할 때 항상 $0$ 이상 $\varphi-1$ 이하가 되도록 정규화해야 한다.

시간 복잡도는 $O(\log M)$이다.