[1629] 곱셈

당연히 반복해서 곱하는거랑 math.pow 는 시간, 메모리 초과임

 

그래서 메모이제이션으로도 풀어봤는데 그것도 메모리 초과임

 

결국 젬민이의 도움을 받았다

 

홀수짝수 구분안하고 제출했더니 틀렸습니다 나와서 홀수 짝수 구분 함

 

짝수는 s(n//2) * s(n//2) 라서 함수 중복호출을 피하기 위해 변수에 넣어야 함

홀수인 경우 짝수의 결과에 s(n%2) 한번만 더 호출해주면 됨

 

시간 아껴보겠다고 함수 밖에서 n//2로 호출했는데 생각해보면 홀수일 땐 또 무용지물이라 그냥 다시 n으로 호출함

 

마지막으로 95%쯤에서 틀렸습니다 라고 떠서 뭘까 했더니 A 자체가 C보다 큰 경우를 생각 못 했다

 

b 가 1일 때 A%C로 바꾸었더니 정답이라고 나왔다 

 

import sys

input = sys.stdin.readline

A, B, C = map(int, input().strip().split())


def solved(b):
    global A
    global C
    if b == 1:
        return A%C
    elif b == 0:
        return 1
    size = b // 2
    t = solved(size) % C
    tt = (t * t) % C
    # 홀수일때
    if b % 2 == 1:
        return (tt* A % C) % C
    return tt


print(solved(B))