파이썬으로 주어진 n에 대한 수열 S의 마지막 자릿수 구하기

문제 설명

값 n이 하나 주어졌을 때, 수열 S의 마지막 자릿수를 구해야 합니다. 수열 S는 다음 식으로 정의됩니다.

$$\sum_{i=0,\: 2^{i}\leqslant n}^{\alpha } \sum_{j=0}^{n} 2^{2^{i}+2j}$$

예를 들어 입력이 n = 2라고 가정해 보겠습니다. 조건 2ⁱ ≤ n을 만족하는 유효한 i 값은 0과 1뿐이므로, 각 항은 다음과 같이 계산됩니다.

• S₀ = 2^(2⁰+0) + 2^(2⁰+2) + 2^(2⁰+4) = 2 + 8 + 32 = 42
• S₁ = 2^(2¹+0) + 2^(2¹+2) + 2^(2¹+4) = 4 + 16 + 64 = 84

두 항의 합은 42 + 84 = 126이며, 따라서 최종 결과의 마지막 자릿수는 6이 됩니다.

접근 방법

지수를 직접 전개하면 값이 기하급수적으로 커져 일반적인 정수 연산으로 처리하기 어렵습니다. 하지만 우리에게 필요한 것은 전체 값이 아니라 마지막 자릿수뿐이므로, 모든 덧셈과 곱셈 과정에서 10으로 나눈 나머지(mod 10)만 추적하면 효율적으로 해결할 수 있습니다. 파이썬의 내장 함수 pow()는 세 번째 인자로 모듈러 값을 전달받아 거듭제곱의 나머지를 한 번에 계산해 주기 때문에 이 문제에 특히 유용합니다.

알고리즘은 다음 단계로 진행됩니다.

• total을 0으로, temp를 1로 초기화합니다.
• temp ≤ n인 동안 다음을 반복합니다.
  • total에 2^temp mod 10을 더합니다.
  • temp를 두 배로 늘립니다. 즉, temp는 1, 2, 4, 8, ... 순으로 변화합니다.
• n이 홀수이면 total에 5(= 1 + 4)를 곱하고, 짝수이면 그대로 둔 뒤 10으로 나눈 나머지를 취합니다.
• total을 반환합니다.

while 루프는 n의 크기에 대해 로그 시간(O(log n))으로 실행되므로 n이 매우 큰 경우에도 빠르게 동작합니다.

구현 예시

아래 파이썬 코드를 통해 해결 과정을 더 명확히 이해할 수 있습니다.

def solve(n):
    total = 0
    temp = 1
    while (temp <= n):
        total += pow(2, temp, 10)
        temp *= 2
    total = total * (1 + (4 if n % 2 == 1 else 0)) % 10
    return total

n = 2
print(solve(n))

입력

2

출력

6