問題一覧 > 通常問題

No.1140 EXPotentiaLLL!

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 221
作問者 : nok0nok0 / テスター : eSeFeSeF
16 ProblemId : 4822 / 出題時の順位表
問題文最終更新日: 2020-07-31 10:22:44

問題文

nok0くんは算数ができません。
困っているnok0くんの代わりに $P$ が素数かを判定し、もし $P$ が素数ならば $A^{P!}$ (mod $P$) を求めてください。

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

【注意】
入出力が多いので高速な入出力を使うことを強くお勧めします。
また、Writer及びTesterでPyPy3を用いて制限時間に余裕を持ってAC出来ることを確認していますが、Python3でAC出来るかは未確認です。
Pythonでの提出には十分ご注意ください。

入力

入力の1行目は以下の通りである。
$T$
そして、続く $T$ 行が $T$ 個のテストケースを表す。これらはそれぞれ以下の形式の行である。
$A$ $P$ 

【制約】
・$1\le T\le 5×10^5$
・$1\le A\le 10^{18}$
・$1\le P\le 5×10^{6}$
・入力は全て整数である。

出力

各テストケースに対し、 $P$ が素数であれば $A^{P!}$ (mod $P$) を、そうでなければ $-1$ を標準出力に出力せよ。
テストケースごとに改行すること。

サンプル

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

1つめのテストケースでは $4$ は素数ではないので $-1$ を出力してください。
2つめのテストケースでは $3$ は素数なので、 $2^{3!} = 64$ を $3$ で割った余りの $1$ を出力してください。

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