[yukicoder] No. 1232 2^x = x

問題

方針

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

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

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

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

が得られます。

\[t(p – 1) \bmod = 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 \) となります。したがって、

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

\[(p-1)^2 \bmod p = 1\]

となります。

コード