問題
T個のテストケースについて、
Pが素数か判定し、素数でなければ-1、素数ならば、A^(P!) mod Pを求めよ。
制約
- 1 <= T <= 5 * 10^5
- 1 <= A <= 10^18
- 1 <= P <= 5 * 10^6
解法
Pが素数かどうかは、素数テーブルを最初に作っておけばO(1)で求められるのでよい。
A^(P!) mod Pは、P! mod PがPが入っているので、常に0になることがわかる。
なので、A^0=1かというと、計算的にAによって他の値も取りうる。
AがPの倍数の場合は、0を何回も掛け合わせることになるので、答えも0になる。
したがって、倍数チェックをして倍数なら0、そうでなければ1となる。
