[파이썬 / 백준 1629번] 곱셈

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

엄청 단순 해 보이는데 계속 시간 초과가 나서 고생했다.

결국 검색해서 알게 되었는데 알고 나니 허무..

 

거듭제곱의 속성을 사용하여 풀면 되는것이었다.

 

예를들어 10^28 을 구하려면, 10을 28번 곱해야 하기 때문에 연산속도가 엄청나게 늘어나게된다.

하지만 10^28은 (10^14)^2와 같기때문에 이런 논리로 구하면 연산이 확실히 줄어들게된다.

 

10^28

=(10^14)^2

=((10^7)^2)^2

=(((10^3)^2*10)^2)^2

=((((10^2)*10)^2*10)^2)^2

 

이런식으로 제곱수를 먼저 구하여서 연산하면 속도가 매우매우 빠루다.

 

def power(A,B):
    if B%2>0:
        return power(A,B-1)*A
    elif B==0:
        return 1
    elif B==1:
        return A
    else:
        result=power(A,B//2)
        return result**2%z

x,y,z=map(int,input().split())
print(power(x,y)%z)