[백준/Python] 1629 - 곱셈

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

풀이
처음에는 제곱수의 1의 자리수가 계속해서 반복되는 특징을 가지고 문제를 풀려고 했으나 잘 풀리지 않았다 ..
찾아보니 분할정복 문제인 만큼 재귀를 이용해서 풀 수 있었다
$A^B$는 B가 짝수라면 $A^{B/2} \times A^{B/2}$로 표현이 가능하다
$A^B$는 B가 홀수라면 $A^{B/2} \times A^{B/2} \times A$로 표현이 가능하다
따라서, B가 1이 될 때 까지 재귀호출을 수행해 작은 문제들을 해결할 수 있다

그리고 pow라는 파이썬의 내장 함수를 사용하면 간단하게 답을 구할 수 있다고 한다
pow(base, exp, mod)의 파라미터를 가지고 있고 결과는 (base**exp)%mod 와 동일하다

코드

import sys

a, b, c = map(int, sys.stdin.readline().split())

def modular(a,b,c):
    if b == 1:
        return a%c
    ans = modular(a,b//2,c)
    if b % 2 == 0:
        return (ans*ans)%c
    else:
        return (ans*ans*a)%c
print(modular(a,b,c))