[백준][Python] 1629번 곱셈 - 실버 1

https://www.acmicpc.net/problem/1629

1629번: 곱셈

문제

풀이

분할 정복을 통한 거듭제곱을 구하는 방법은 재귀문과 반복문으로 2개로 이루어져있습니다.
그 중 저는 반복문을 이용하여 문제를 풀어주었습니다.

자세한 분할정복을 통한 거듭제곱을 구하는 알고리즘에 대한 글은 아래 링크를 참고해주세요:

https://sunghyun98.tistory.com/313

[알고리즘] 분할 정복을 이용한 거듭제곱

 

코드

# 1629번 곱셈

a, n, c = map(int, input().split())
ans = 1

while n:
    # 만일 홀수 번 거듭제곱이 이뤄진다면 지수를 짝수로 만들어주기 위해
    # 답이 될 변수에 a를 한 번 곱해준다. n(지수)는 n //= 2에서 짝수로 만들어준다.
    if n % 2:
        ans *= a
        ans %= c
        
    a *= (a%c)
    n //= 2
    
print(ans)

 

출력결과