[BOJ_Silver 1] 1629 - 곱셈 [python]

$A^{B} Mod C$의 값을 구하는 문제입니다.

A를 for문으로 B번만큼 곱하는 동시에 C로 나머지를 구해준다면 편하겠지만 

 

A, B, C는 모두 2,147,483,647 이하의 자연수이므로, 시간 초과가 발생합니다.

 

때문에, A^B의 값을 보다 빠르게 구하기 위해 아래의 함수를 사용할 필요가 있습니다.

 

def Func(A,B):

   if  B == 0:  return $1$

   elif  B % 2:  return $Func(A,B//2)^2 * A$

   return  $Func(A,B//2)^2$

 

간단한 예시를 들어, F(2,6)의 경우

1) Func(2,6)

2) Func(2,3)

3) Func(2,1)

4) Func(2,0)의 단계를 밟으며, $2^6$의 값을 총 4번의 함수 호출로 구할 수 있습니다.

 

한번 함수가 진행할때마다 차수가 2로 나누어지므로, 결과적으로,

다음의 함수는 O(logN + 1) = O(logN)의 시간 복잡도를 가집니다.

 

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


def getMod(A,B):
    if not B:
        return 1

    value = getMod(A, B // 2) ** 2

    if B % 2: value *= A % C

    return value % C

print(getMod(A,B))