The Legend Math EXAM

解説

1995年の京都大学文系後期第四問の内容を拡張した問題となっています。$n$ の値をfor文で回せば解けますが、どの範囲で回せばよいのでしょうか？

一旦$f(n)$を整理してみます。

$f(n) = 1^n + 2^n + ... + p^n (mod$ $p)$

ここで唐突にフェルマーの小定理を思い出してください。

$a^{p-1} \equiv 1 (mod$ $p) \Leftrightarrow a^p \equiv a$ ( $a$ は $p$ と互いに素 )

これにより、$k^n \equiv k^{(n-p+1)}$ が成り立つので $f(n) \equiv f(n-p+1)$ となり、結局 $n \leq p-1$ の範囲でだけ $n$ を回せばよいと分かります。

時間計算量は1つの $n$ について $f(n)$ を求めるのに $O(plog(p))$ かかるので、$O(p^2log(p))$ となります。

別解

実は、$f(n)$ $mod$ $p$ の最大値は $n \equiv 0 (mod$ $p-1)$ のときで $p-1$ となります。これは、先ほどのフェルマーの小定理　$a^{p-1} \equiv 1 (mod$ $p)$ ( $a$ は $p$ と互いに素 ) を用いることで　$f(n) = 1 \times (p-1) + p^n (mod$ $p) \equiv p-1$ と $f(n)$ を式変形して示せます。

余談ですが、$n \equiv 0 (mod$ $p-1)$ でないときは $f(n)$ $mod$ $p$ の値が $0$ となります。これは巡回群の性質から示せますが、私もそんなに理解できていません。