1. はじめに
本記事では、Project Euler の問題番号48の Self Powersの解説を行う。
2. 問題文と目的
The series, $1 ^ 1 + 2 ^ 2 + 3 ^ 3 + \dots + 10 ^ {10} = 10405071317$.
Find the last ten digits of the series, $1 ^ 1 + 2 ^ 2 + 3 ^ 3 + \dots + 1000 ^ {1000}$.
つまり、$1 ^ 1 + 2 ^ 2 + 3 ^ 3 + \dots + 1000 ^ {1000}$ の下位10桁を求める必要がある。単純に計算すると、数値が非常に大きくなりオーバーフローが発生してしまう。しかし、求めるのは末尾10桁のみであるため、$MOD = 10^{10}$ として各項ごとに剰余を取りながら計算すれば、効率的に解くことができる。
コードは以下の通りとなる。
def sigma(start, end, mod):
result = 0
for i in range(start, end + 1):
# i^i mod 10^10 を加算
result = (result + pow(i, i, mod)) % mod
return result
MOD = 10 ** 10
print(sigma(1, 1000, MOD))
実行結果は次の通りである。
9110846700
3. 参考リンク
[1] Project Euler.net