[Python 3] BOJ - 1629 "곱셈"

  # 문제 링크 : https://www.acmicpc.net/problem/1629

1629번: 곱셈

 # 풀이 :

 개인적으로 이 문제는 이진수를 이용하는 것이라 생각한다. 물론 파이썬 내장 함수중 pow(x,y,z)를 통해서 한 줄만에 해결할 수 있지만, 이진수를 이용하여 a의 b승을 c로 나눈 나머지를 구하는 방식은 차후에 행렬의 제곱에서도 유효하기 때문에 이진수를 이용한 방법을 통해 푸는것이 낫다.

 a의 19승을 구하는 경우를 생각해보자. 선형으로 계속 a를 곱해나가면 19번의 곱셈이 필요하므로 만일 문제의 입력이 극단적으로 커지는 경우는 시간초과를 피할 수 없다.

<그림 1. a의 19승>

 그림 1에서 19를 이진수로 나타내면 1101(2)이다. 따라서 a의 16승과 a의 2승, a의 1승을 합하면 3번의 연산만에 19승을 구할 수 있다. 따라서 a의 b승을 log(b)만에 구할 수 있다. 그런데 b를 2로 나눈 나머지의 여부에 따라 곱해지는 수가 달라지므로 b를 2로 나눈 나머지가 1일 때 곱하는 부분이 필요하다.

<그림 2. 나머지에 따른 승수>

 그런데 나머지 1일 때마다 a를 계속 곱해주면 a는 3번밖에 곱해지지 않는다. 그런데 나머지가 1이든 아니든 간에 a를 계속 곱해주면 a의 1승, 2승, 4승, 8승.. 을 구할 수 있다. 따라서 나머지에 상관없이 a는 곱해주면서 나머지가 1일 때는 다른 변수에 현재 곱해진 a를 곱해주면 정답을 구할 수 있다

<그림 3. 정답을 구하는 과정>

 # 코드

import sys

# 입력부
a,b,c = map(int, sys.stdin.readline().split())

# pow : a의 b승을 c로 나눈 나머지를 리턴하는 함수
def pow(a,b,c):
    # res : 결과값으로 초기값은 곱셈의 역원인 1로 초기화
    res = 1
    while b:
        # 만일 b를 2로 나눈 나머지가 1이면
        if b % 2:
            # res에 a를 곱해주고 나머지 연산
            res = (res * a) % c
        # 나머지에 상관없이 res에 올바른 a를 곱해주기 위해 a를 제곱하고 나머지 연산
        a = (a * a) % c
        # 이진수로 나타내기 위해 b를 계속 2로 나누어 준다
        b //= 2
    return res
    
# 정답 출력
print(pow(a,b,c))