Project Euler 48

プロジェクトオイラー
http://projecteuler.net/index.php

Q48.
11 + 22 + ... + 10001000

こうすれば答えは出る。


N = 1000
print str(sum(map(lambda x: x ** x, range(1, N + 1))))[-10:]

しかし、多倍長整数を使っているのが気に入らない。
下10桁しか使わないので、4桁で区切って要素最大3つのリストにして計算すれば、4バイトの整数の範囲内で計算できる。加算・乗算だけなので簡単。しかし、かえって遅くなった。



import copy
N = 1000
M = 10
limits = [ 10**4 ] * ((M-1)/4) + [ 10**((M-1)%4+1) ]
length = len(limits)

def mul(x, y):
dim = min(length, len(x) + len(y))
z = [ 0 for i in range(dim) ]
for i in range(len(x)):
for j in range(len(y)):
d = i + j
if d < length:
z[d] += x[i] * y[j]
normalize(z)
return z

def add(x, y):
z = copy.copy(x)
for i in range(min(len(x), len(y))):
z[i] += y[i]
if len(x) < len(y):
for i in range(len(x), len(y)):
z.append(y[i])
normalize(z)
return z

def normalize(x):
overflow = 0
for i in range(len(x)):
x[i] += overflow
overflow = x[i] / limits[i]
x[i] -= overflow * limits[i]

def pow(x, n):
if n == 1:
return x

y = pow(x, n / 2)
y = mul(y, y)
if n & 1:
y = mul(x, y)
return y

def toString(a):
return "".join(map(str, reversed(a)))

print toString(reduce(add, map(lambda n: pow([ n ], n), range(1, N + 1))))