백준 3944 나머지계산 (Python, Pypy)

#3944 나머지계산
import sys

input = sys.stdin.readline
N = int(input())
A = []
for i in range (0,N):
    a,b = input().split()
    a = int(a)
    A.append([a,b])

for i in range (0,N):
    result = 0
    for j in range (0,len(A[i][1])):
        result += int(A[i][1][j]) % (A[i][0]-1)

    result %= (A[i][0]-1)

    print(result)

Pypy로는 시간내로 나오는데 Python으로는 잘 안 나와서 슬픈 상황.

아이디어로는, b진법 수를 10진법으로 변환시켜서 생각하고,
그것을 b-1로 나눈 나머지를 구하는 것이므로
각 자릿수의 합을 구한 뒤 b-1로 나누어 달라는 것과 다를 것이 없다.

예를 들어,
888이 9진법으로 나타내어져있을때, 이를 10진법으로 나타낸다면
8(9^2) + 8(9) + 8인데
이를 8 (9-1)로 나눈 나머지를 구한다면
윗 식의 각 항에 대하여 8로 나눈 나머지가 되므로
8(1^2) + 8(1) + 8 = 24 를 8로 나눈 나머지,
즉, 0이 나오게 되는 것이다.