[yukicoder] No. 1232 2^x = x

2020年9月19日2020年12月13日

問題

方針

\( p = 2 \) のときは \( x = 2 \) が答えとなります。それ以外について考えます。フェルマーの小定理より、

\[2^{p-1} \bmod p = 1\]

となるので、自然数 \( t \) について、

\[ 2^{t(p – 1)} \bmod p = 1\]

となります。ここで、

\[t(p – 1) \bmod p = 1\]

を満たす \( t \) について考えると、

\begin{eqnarray}
t(p – 1) \bmod p &=& 1\\
-t \bmod p &=& 1\\
(p – t) \bmod p = 1
\end{eqnarray}

となるので、\( p -t = 1 \) より、\( t = p – 1 \) となります。したがって、

\begin{eqnarray}
2^{(p – 1)^2} \bmod p &=& 1\\
(p-1)^2 \bmod p &=& 1
\end{eqnarray}

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll p[N];
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    for (int i = 0; i < N; i++) {
        if (p[i] == 2) {
            cout << 2 << "\n";
        } else {
            ll t = p[i] - 1;
            cout << t * t << "\n";
        }
    }
    return 0;
}