EXPotentiaLLL! [yukicoder 1140]

https://yukicoder.me/problems/no/1140

前提知識

• 素数判定
• フェルマーの小定理

解説

https://yukicoder.me/submissions/522953

難しい問題に見える。要求事項として、以下がある。

• Pが素数かを判定
• Pが素数ならmodP上で、AのP!乗を計算せよ

Pが素数かを判定

素数判定には色々やり方があるが、Pの上限は5×10⁶なので、
エラトステネスの篩で前計算しておいて、素数判定はO(1)とするのがいい。
まあ、この辺は頑張ってほしい。

AのP!乗？

普通に計算するのは無理というのは何となく分かる。
累乗のmod Pは見覚えが無いだろうか？
そう。フェルマーの小定理である。

A^{P!}
= A^{P(P-1)(P-2)!}
= (A^{P-1})^{P(P-2)!}
= 1^{P(P-2)!}
= 1

このように言い換えることができるので、基本的には答えは1になる。
コーナーケースとしてA mod Pが0の場合がある。

ll A; int P;
vector<bool> primes;
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> A >> P;

    if (!primes[P]) {
        printf("-1\n");
        return;
    }

    if (A % P == 0) printf("0\n");
    else printf("1\n");
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    primes = makePrimesBool(5010101);
    rep(t, 0, T) solve();
}