No.981 一般冪乗根

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 10
作問者 : 37zigen37zigen / テスター : keymoonkeymoon
2 ProblemId : 3866
問題文最終更新日: 2020-03-26 22:49:34

問題文

$p$を素数とする。$x^k \equiv a \bmod p$の解を一つ求めよ。解が存在しなければ$-1$を出力せよ。

入力

$T$
$p_1$ $k_1$ $a_1$
$p_2$ $k_2$ $a_2$
$\vdots$
$p_T$ $k_T$ $a_T$

$T$個のテストケースが与えられる。 $i$番目のテストケースに対して$x^{k_i} \equiv a_i \bmod p_i$の解を一つ出力せよ。解が存在しなければ$-1$を出力せよ。
$1 \leq T \leq 1000$
$1 \leq k_i \leq 1000$
$2\leq p_i\leq 10^9+7$
$1 \leq a_i < p_i$

問題公開後に新たなアルゴリズムの高速化が分かったため
$1 \leq T \leq 1000$
$1 \leq k_i \leq 10^9$
$2\leq p_i\leq 10^{18}$
$1 \leq a_i < p_i$
のテストケースが追加されました(2020/02/10)。evilケースとして追加されているのでステータスに影響はしません。

更に以下のケースがevil_hardとして追加されました(2020/02/13)。
$1 \leq T \leq 1000$
$1 \leq k_i < p$
$2\leq p_i\leq 10^{18}$
$1 \leq a_i < p_i$

出力

$x^{k_i} \equiv a_i \bmod p_i$の解を各行に出力してください。 ただし、解が存在しなければ$-1$を出力してください。 最後に改行してください。

サンプル

サンプル1
入力
1
13 2 4
出力
11

$11^2\equiv4\bmod 13$である。$2^2\equiv4\bmod 13$だから$2$を出力してもよい。

サンプル2
入力
1
3 2 2
出力
-1

$x^2\equiv2\bmod 3$を満たす$x$は存在しない。

サンプル3
入力
10
23 6 19
19 9 14
23 10 7
31 7 25
29 6 20
19 7 14
19 7 12
31 2 5
19 8 9
29 9 11
出力
-1
-1
-1
25
16
2
12
25
17
19

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。