[파이썬] [백트래킹] 백준 1629 곱셈

코드

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

1629번: 곱셈

 

코드

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

def make(a,b):
    if b == 1: # b의 값이 1이면 a % C를 return한다.
        return a % c
    else:
        temp = make(a, b // 2) # a^(b // 2)를 미리 구한다.
        if b % 2 == 0:
            return temp * temp % c # b가 짝수인 경우
        else:
            return temp * temp * a % c # b가 홀수인 경우

print(make(a,b))