Fractional Power

Let $M=998244353$. Since $M$ is prime, every integer not divisible by $M$ has a modular inverse modulo $M$.

By Fermat's little theorem, if $a \not\equiv 0 \pmod M$, then

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

Therefore, when computing powers of nonzero numbers modulo $M$, only the exponent modulo

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

matters.

The condition gives

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

Thus, $q$ has an inverse modulo $\varphi$. That is, there exists an integer $r$ such that

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

The original equation is

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

Raise both sides to the power $r$:

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

Then

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

Since $qr \equiv 1 \pmod \varphi$, Fermat's little theorem gives

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

Therefore,

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

So there is exactly one possible value of $x$, and the answer is

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

Here, $q^{-1}$ is not the inverse modulo $M$, but the inverse modulo $M-1$.

The algorithm is as follows.

• Set $\varphi = 998244352$.
• Normalize $p$ modulo $\varphi$ to obtain $P$.
• Normalize $q$ modulo $\varphi$, then compute its inverse using the extended Euclidean algorithm.

Be careful that $998244352$ is not prime. Therefore, $q^{-1} \pmod {998244352}$ must not be computed using Fermat's little theorem. Use the extended Euclidean algorithm instead.

Also, $p$ and $q$ may be negative, so remainders must be normalized into the range from $0$ to $\varphi-1$.

The time complexity is $O(\log M)$.