No.1140 EXPotentiaLLL!
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
nok0
eSeF