[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)

<正しいコード>

時間を減らすために,関数再試行時に残りを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))