Project Euler 48

题目

Self powers

The series, $1^1 + 2^2 + 3^3 + … + 10^{10} = 10405071317$.

Find the last ten digits of the series, $1^1 + 2^2 + 3^3 + \dots + 1000^{1000}$.

解决方案

快速幂算法，可以在$O(\log m)$的时间复杂度内计算$a^m \% p$的值。

Python代码如下：

def quick_power(a: int, m: int, p: int):
    ans = 1
    while m > 0:
        if m & 1:
            ans = ans * a % p
        a = a * a % p
        m >>= 1
    return ans

这个算法本质上是将幂$m$看作是二进制位。

并且，$a^{2^i}$可以很容易地由$a^{2^{i-1}}$计算出：$a^{2^i}=(a^{2^{i-1}})^2$。

因此，将幂指数$m$看作是二进制数，如果第$i$位上是$1$，那么就将结果乘上$a^{2^i}$。将所有值累乘起来就得到答案。

由于Python自带pow(a,m,p)，因此直接调用即可。

代码

N = 1000
mod = 10000000000
ans = 0
for i in range(1, N + 1):
    ans = (ans + pow(i, i, mod)) % mod
print("{:09}".format(ans))