[백준] 1629번 곱셈 (Python)

문제

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

입력

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

출력

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

---

아이디어

이 문제를 풀기 위해서는 나머지 분배 법칙을 알고있어야 한다.

나머지 분배 법칙 
(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p

문제의 예시를 사용하여 a=10, b=11, c=12라고 하자.
구하고자 하는 것은 (10^11)%12이고 이 식을 다음과 같은 과정으로 바꿀 수 있다.

(10^5 x 10^5 x 10)%12 
= ((10^5%12) x (10^5%12) x (10%12))%12
= {((10^2%12) x (10^2%12) x (10%12))%12 
  x ((10^2%12) x (10^2%12) x (10%12))%12 x (10%12)}%12

코드

import sys
input = sys.stdin.readline

a,b,c = map(int,input().split())

def f(x,n):
  if n==1:
    return x%c
  t = f(x,n//2)
  if n%2==0:
    return (t*t)%c
  else:
    return (t*t*x)%c

print(f(a,b))