오일러 프로젝트 48

1^1 + 2^2 + 3^3 + … + 10^10 = 10405071317 입니다.
 
1^1 + 2^2 + 3^3 + … + 1000^1000 의 마지막 10자리 숫자는 무엇입니까?

http://euler.synap.co.kr/prob_detail.php?id=48

접근

큰 정수가 등장하는 문제에서는 파이썬과 같이 큰 정수를 지원하는 언어를 사용하면, 너무 반칙같은 기분이 든다.

%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)