問題一覧 > 通常問題

No.1140 EXPotentiaLLL!

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 312
作問者 : nok0 / テスター : eSeF
お気に入りにしたユーザー ProblemId : 4822 / 自分の提出
問題文最終更新日: 2020-07-31 10:22:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 259 (順位表) の他の問題:

Problem Statement

nok0 is bad at arithmetic.
On behalf of the troubled nok0, determine whether $P$ is prime, and if $P$ is prime, find $A^{P!}$ (mod $P$).

Answer for $T$ test cases.

[Note]
Since the amount of input and output is large, we strongly recommend using fast I/O.
Also, the Writer and Tester have confirmed that an AC is achievable with PyPy3 with plenty of margin within the time limit, but it is unconfirmed whether an AC is possible with Python3.
Please be very careful when submitting in Python.

Input

The first line of the input is as follows.
$T$
The following $T$ lines represent the $T$ test cases. Each of them is a line of the following format.
$A$ $P$ 

[Constraints]
・$1\le T\le 5×10^5$
・$1\le A\le 10^{18}$
・$1\le P\le 5×10^{6}$
・All inputs are integers.

Output

For each test case, print $A^{P!}$ (mod $P$) to standard output if $P$ is prime, and $-1$ otherwise.
Print a newline after each test case.

Sample

Sample 1
Input
2
33 4
2 3
Output
-1
1

In the first test case, $4$ is not prime, so print $-1$.
In the second test case, $3$ is prime, so print $1$, the remainder when $2^{3!} = 64$ is divided by $3$.

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