No.1287 えぬけー

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.1287 えぬけー

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 106
作問者 :

tyawanmusi / テスター :

chineristAC

12 ProblemId : 5241 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2020-11-14 19:20:12

問題文

整数 $X, K$ が与えられます。

$X = N^{K} \mod (10^{9} + 7)$ となる整数 $N$ を求めて下さい。

$T$ 個のテストケースについて答えてください。

制約

$X, K, T$ は整数
$1 \leq T \leq 10^{5}$
$0 \leq X < 10^{9} + 7$
$1 \leq K \leq 5 \times 10^{8}$
$K$ は奇数

入力

$T$

最初にテストケースの個数である整数 $T$ が $1$ 行に入力されます。

その後に、 $T$ 行に渡って次のように入力されます。

 $X$   $K$

整数 $X, K$ が空白区切りで $1$ 行に入力されます。

出力

各テストケースについて、次のように出力してください。

整数 $N$ を $1$ 行に出力してください。最後に改行してください。

ここでの $N$ は、以下の制約を満たしている必要があります。

$0 \leq N < 10^{9} + 7$
$X = N^{K} \mod (10^{9} + 7)$

与えられる入力及びこの制約において、解がただ一つ存在することが証明できます。

サンプル

サンプル1

入力

出力

2
10
16

$32 = 2^{5}$ , $1000 = 10^{3}$ , $4096 = 16^{3}$ です。

サンプル2

入力

3
1000000000 1
1000000000 3
1000000000 9

出力

1000000000
1000
10

$1000000000 = 1000000000^{1}$ , $1000000000 = 1000^{3}$ , $1000000000 = 10^{9}$ です。

サンプル3

入力

3
1000000006 11
1000000006 13
1000000006 15

出力

1000000006
1000000006
1000000006

サンプル4

入力

5
337716880 91488205
413500684 972383
499738548 34626483
901106148 239798535
230314780 62951413

出力

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

yukicoder

No.1287 えぬけー

問題文

制約

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力

サンプル4

入力

出力