BOJ 3944 - 나머지 계산

문제

BOJ 3944 - 나머지 계산

b진법 수 d를 (b-1)로 나눈 나머지를 구하라.

입력

테스트 케이스 수 T, 각 케이스에 진법 b와 수 d가 주어진다.

출력

각 케이스마다 d mod (b-1)의 결과를 출력한다.

예제

풀이

자릿수 합의 나머지 성질을 이용하여 계산한다.

1. b진법 수 d의 각 자릿수를 10진수로 변환하여 합산한다
2. 그 합을 (b-1)로 나눈 나머지가 답이다

핵심 아이디어: b진법에서 b ≡ 1 (mod b-1)이므로, d mod (b-1)은 각 자릿수의 합 mod (b-1)과 같다 (10진법에서 9로 나눈 나머지 = 자릿수 합 mod 9와 동일한 원리).

코드

t = int(input())
 
for _ in range(t):
    b, d = input().split()
    b = int(b)
    tmp = sum(map(int, list(d)))
    print(tmp % (b - 1))

복잡도

• 시간: O(T * len(d))
• 공간: O(1)