파이썬으로 숫자를 n번 이어 붙여 만든 수의 모듈로 값 구하기

문제 개요

숫자 A가 주어졌을 때, 이 숫자를 n번 반복해 이어 붙여 아주 큰 수 X를 생성하고, 그 값의 X mod m(m으로 나눈 나머지)을 구하는 것이 목표입니다.

예를 들어 입력이 A = 15, n = 3, m = 8이라면, 이어 붙인 수 X는 151515가 되며, 151515 ÷ 8의 나머지는 3이므로 출력값은 3입니다.

접근 방법

X는 자릿수가 매우 커질 수 있으므로 실제로 문자열을 이어 붙이는 것은 비효율적입니다. 대신 수학적 성질을 활용하면 다음과 같이 정리할 수 있습니다.

• k를 A의 자릿수라고 하면, X = A × (10^(k(n−1)) + 10^(k(n−2)) + ... + 10^k + 1) 형태로 표현됩니다.
• 이 등비수열의 합은 X = A × (10^(kn) − 1) / (10^k − 1) 로 압축됩니다.
• 모듈로 연산에서는 나눗셈을 직접 처리할 수 없으므로, 분모 d = 10^k − 1 을 포함한 d × m을 새로운 모듈러스로 사용해 계산합니다.
• d × m 기준으로 나머지를 구한 뒤 d로 나누면, 원하는 X mod m을 정확히 얻을 수 있습니다.

알고리즘 단계

• A가 0이면 0을 반환합니다.
• an := A, c := A의 자릿수로 초기화합니다.
• c := 10^c, d := c − 1 로 설정합니다.
• newmod := d × m 으로 새로운 모듈러스를 정의합니다.
• val := (c^n mod newmod) − 1 을 계산하고, 음수가 되지 않도록 (val + newmod) mod newmod 로 보정합니다.
• an := (an × val) mod newmod 를 구합니다.
• 마지막으로 an을 d로 나눈 몫(floor)을 반환합니다.

파이썬 구현 예제

def solve(A, n, m):
   if A == 0:
      return 0
   an = A
   c = len(str(A))
   c = 10 ** c
   d = c - 1
   newmod = d * m
   val = pow(c, n, newmod) - 1
   val = (val + newmod) % newmod
   an = (an * val) % newmod
   return an // d

A = 15
n = 3
m = 8
print(solve(A, n, m))

입력

15, 3, 8

출력

3

정리

이 방법은 거듭제곱의 모듈러 연산(pow 함수의 세 인자 버전)을 활용하기 때문에, 이어 붙인 수가 아무리 커져도 시간 복잡도는 O(log n) 수준으로 매우 효율적입니다. 문자열 조작 없이도 큰 수의 나머지를 안전하게 계산할 수 있다는 점이 핵심입니다.