8995: [yosupo] Number Theory - Kth Root (Mod)
[Creator : ]
Description
Each test case consists of $T$ cases.
Given $K, Y, P(P: \textrm{prime})$.
Print any $X$ s.t. $X^K \equiv Y \pmod{P}$, or $-1$ if there is no such $X$.
We note that $0^0\equiv 1 \pmod{P}$ in this problem.
Given $K, Y, P(P: \textrm{prime})$.
Print any $X$ s.t. $X^K \equiv Y \pmod{P}$, or $-1$ if there is no such $X$.
We note that $0^0\equiv 1 \pmod{P}$ in this problem.
Input
$T$
$K_0$ $Y_0$ $P_0$
$K_1$ $Y_1$ $P_1$
$\vdots$
$K_{T-1}$ $Y_{T-1}$ $P_{T-1}$
$K_0$ $Y_0$ $P_0$
$K_1$ $Y_1$ $P_1$
$\vdots$
$K_{T-1}$ $Y_{T-1}$ $P_{T-1}$
Output
For each line, print $X$ or $-1$.
Constraints
$1 \leq T \leq @{param.T_MAX}$
$0 \leq K \leq @{param.K_MAX}$
$2 \leq P \leq @{param.P_MAX}$
$0 \leq Y < P$
$P$ is prime
$0 \leq K \leq @{param.K_MAX}$
$2 \leq P \leq @{param.P_MAX}$
$0 \leq Y < P$
$P$ is prime
Sample 1 Input
5
0 10 11
10 9 11
1 1 2
5 4 13
0 8 11
Sample 1 Output
-1
-1
1
10
-1