No.1287 えぬけー
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 :
tyawanmusi
/ テスター :
chineristAC
タグ : / 解いたユーザー数 105
作問者 :
tyawanmusi
/ テスター :
chineristAC
問題文最終更新日: 2020-11-14 19:20:12
問題文
整数 $X,K$ が与えられます。
$X = N^K\ \mathrm{mod}\ (10^9+7)$ となる整数 $N$ を求めて下さい。
$T$ 個のテストケースについて答えてください。
制約
- $X,K,T$ は整数
- $1 \le T \le 10^5$
- $0 \le X < 10^9+7$
- $1 \le K \le 5 \times 10^8$
- $K$ は奇数
入力
$T$
最初にテストケースの個数である整数 $T$ が $1$ 行に入力されます。
その後に、 $T$ 行に渡って次のように入力されます。
$X$ $K$
整数 $X,K$ が空白区切りで $1$ 行に入力されます。
出力
各テストケースについて、次のように出力してください。
整数 $N$ を $1$ 行に出力してください。最後に改行してください。
ここでの $N$ は、以下の制約を満たしている必要があります。
- $0 \le N < 10^9+7$
- $X = N^K\ \mathrm{mod}\ (10^9+7)$
与えられる入力及びこの制約において、解がただ一つ存在することが証明できます。
サンプル
サンプル1
入力
3
32 5
1000 3
4096 3
出力
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
出力
314159265
358979323
846264338
327950288
419716939
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。