[Python] 백준 1629_ 곱셈

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

<틀린 코드 - 시간초과>

import sys
input = sys.stdin.readline

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

def cal(a,b):
    if b==1:
        return a
        
    if b%2==0: #짝수이면
        return cal(a,b//2)**2      
    else: #홀수이면
        return cal(a,b//2)**2*a
    
print(cal(a,b)%c)

<맞은 코드>

시간을 줄여주기 위해 함수를 retrun할때 미리 c로 나눈 나머지를 리턴해준다.
마지막 결과값에 c로 나누는것보다 시간을 줄일 수 있다.

import sys
input = sys.stdin.readline

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

def cal(a,b,c):
    if b==1:
        return a%c
    
    if b%2==0: #짝수이면
        return (cal(a,b//2,c)**2)%c
    else:#홀수이면
        return (cal(a,b//2,c)**2*a)%c
print(cal(a,b,c))