Project Euler [Problem 48]

剰余は維持されるよという話じゃな

暗号ではおなじみ。

問題

Self powers

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

私訳

自身の冪

1から10までのそれ自身の冪級数は, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317 である。

以下の冪級数の下10桁を求めよ。 1¹ + 2² + 3³ + ... + 1000¹⁰⁰⁰.

解答方針

10¹⁰ で割った剰余を求めればよい。 a*b mod m = (a mod m) * (b mod m) であることを利用する。

あとは、計算時間を早くするために k 乗を log k で実行するくらいか。