1^1 + 2^2 + 3^3 + … + 10^10 = 10405071317 입니다.
http://euler.synap.co.kr/prob_detail.php?id=48
1^1 + 2^2 + 3^3 + … + 1000^1000 의 마지막 10자리 숫자는 무엇입니까?
접근
큰 정수가 등장하는 문제에서는 파이썬과 같이 큰 정수를 지원하는 언어를 사용하면, 너무 반칙같은 기분이 든다.
%time print(str(sum(x*x for x in range(1, 1000)))[-10:])
# CPU times: total: 0 ns
# Wall time: 10.1 ms
# '9110846700'
문자열을 사용한 큰 정수 연산
16번 문제를 풀이하면서 큰 정수를 문자열로 대체하여 곱셈과 덧셈을 하는 함수를 만들어 본 적이 있다. 이 때 작성한 함수를 사용하면 어떨까? 굉장히 시간이 오래 걸리게 된다. 단 문제에서는 한 가지 힌트를 주었는데, 문제에서 필요한 값은 마지막 10자리 만 있으면 된다. 큰 두 수의 곱셈에서 마지막 10자리만 필요하다면, 곱하는 두 수의 끝 열자리 범위에서만 곱하면, 그 답은 10~11자리가 된다. 이렇게하면 전체 연산에서 사용하지 않을 값에 대한 막대한 연산 회수를 크게 줄일 수 있다.
먼저 합과 곱셈 함수를 다시 작성하자. 특히 곱셈에서는 미지막 10자리씩만 계산하고 그 결과도 10자리만 남도록 한다.
_parse = lambda s: [int(c) for c in s[::-1]]
_compose = lambda xs: ''.join(chr(x + 48) for x in xs[::-1])
def s_add(*args):
# 한 번에 여러 수를 덧셈할 수 있도록 개
l = max(map(len, args))
ks = map(lambda a: _parse(a.zfill(l)), args)
res, z = [], 0
for xs in zip(*ks):
z, w = divmod(sum(xs) + z, 10)
res.append(w)
if z > 0:
res.append(z)
return _compose(res)
def _s_multi(a: str, b: str) -> str:
xs = _parse(a)[-10:]
ys = _parse(b)[-10:]
res = []
for i, y in enumerate(ys):
temp = [0] * i
z = 0
for x in xs:
z, w = divmod(x * y + z, 10)
temp.append(w)
if z > 0:
temp.append(z)
res.append(_compose(temp))
return s_add(*res)[-10:]
def _s_pow(x: str, n: int) -> str:
if n == 0:
return "1"
if n == 1:
return x
w = _s_pow(x, n // 2)
w = _s_multi(w, w)
if n % 2 > 0:
w = _s_multi(w, x)
return w
그리고 이렇게 실행하면 전체를 계산하는 것보다 훨씬 빨리 답을 구할 수 있다.
%%time
k = "0"
for i in range(1, 1001):
t = _s_pow(str(i), i)
k = s_add(k, t)[-10:]
print(k)