두 개의 수 n과 m이 주어졌을 때, 1이 n개 이어진 수(예: n=4라면 1111)를 m으로 나눈 나머지를 구하는 것이 목표입니다.
예를 들어 n = 4, m = 27이 입력으로 주어지면 출력은 4가 됩니다. 왜냐하면 1111 mod 27 = 4이기 때문입니다.
문제 해결 접근 방법
n이 매우 커질 경우, 실제로 1을 n개 이어 붙인 수를 만드는 것은 비효율적이거나 불가능할 수 있습니다. 따라서 다음과 같은 수학적 성질을 활용합니다.
1이 n개 이어진 수(레퓨닛, Repunit)는 다음과 같이 표현할 수 있습니다.
R(n) = (10^n − 1) / 9
여기서 핵심 아이디어는 (10^n mod 9m)의 결과를 9로 나눈 몫이 곧 R(n) mod m과 같다는 점입니다. 이를 통해 거듭제곱 계산만으로 나머지를 빠르게 구할 수 있습니다.
또한 큰 지수의 거듭제곱에 대한 나머지를 효율적으로 계산하기 위해 분할 정복 기반의 모듈러 거듭제곱(빠른 거듭제곱) 알고리즘을 사용합니다.
util(x, n, m) 함수의 동작 과정
- y를 1로 초기화합니다.
- n이 0보다 큰 동안 반복합니다.
- n이 홀수이면 y := (y * x) mod m 으로 갱신합니다.
- x := (x * x) mod m 으로 갱신하고, n을 절반으로 줄입니다(n := n // 2).
- 반복이 끝나면 y를 반환합니다.
메인 함수에서는 util(10, n, 9 * m)의 결과를 9로 나눈 몫을 반환하면 됩니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
def util(x, n, m):
y = 1
while n > 0:
# 현재 비트가 1이면(홀수이면) 결과에 곱함
if n & 1:
y = (y * x) % m
# 밑을 제곱하고 지수를 절반으로 줄임
x = (x * x) % m
n >>= 1
return y
def solve(n, m):
return util(10, n, 9 * m) // 9
n = 4
m = 27
print(solve(n, m))입력
n = 4, m = 27
출력
4
코드 설명
util 함수는 밑(base) x를 지수(exponent) n번 곱한 값의 mod m을 O(log n) 시간 복잡도로 계산하는 빠른 거듭제곱 함수입니다. 지수를 이진수로 분해하여, 각 비트가 1일 때마다 결과값에 해당 거듭제곱 값을 곱하는 방식으로 동작합니다.
solve 함수는 앞서 설명한 수학적 성질을 적용합니다. 10^n mod 9m을 구한 뒤 9로 나누면, 1이 n개 이어진 수를 m으로 나눈 나머지를 얻을 수 있습니다. 이 방법은 n이 수억 단위처럼 아주 커져도 숫자를 직접 만들 필요 없이 즉시 답을 구할 수 있다는 장점이 있습니다.