Kth Root(Mod)

AC一覧

Problem Statement
問題文

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.

この問題は $T$ ケース与えられます。

$K, Y, P(P: \textrm{prime})$ が与えられます。

$X^K \equiv Y \pmod{P}$ なる $X$ を1つ求めてください。

ただし $0^0\equiv 1 \pmod{P}$ とします。

Constraints
制約

Input
入力

$T$
$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$.

各行に、$X$、もしくは条件を満たす $X$ が存在しないならば $-1$ を出力してください。

Sample
サンプル

# 1

5
0 10 11
10 9 11
1 1 2
5 4 13
0 8 11
-1
-1
1
10
-1

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions