167. 1629(곱셈) - 파이썬

import sys
input = sys.stdin.readline

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


def power(A, B, C):
    if B == 0:
        return 1

    tmp = power(A, B//2, C)

    if B % 2 == 1:
        return (tmp * tmp * A) % C
    else:
        return (tmp * tmp) % C


print(power(A, B, C))

문제요약

A,B,C가 주어지는데 A를 B번 곱한 값을 C로 나누어라 (A,B,C <= 2,147,483,647)

설명

수가 매우매우 크기 때문에 온전히 A를 B번 곱하면 시간초과가 발생할 수 밖에 없다.

따라서 분할정복을 사용하면 된다.

 

제곱에는 특징이 있다.

다음과 같이 11승을 단 3번만으로 연산을 끝낼 수 있다. O(log N)

 

단, 두가지 경우를 생각해야한다.

1. 지수가 짝수일 때

예를 들어  2^10인 경우 2^5 * 2^5로 나타낼 수 있다.

N^(k/2) * N^(k/2)

 

2. 지수가 홀수일 때

예를 들어 2^11인 경우 2^5 * 2^5 * 2 로 나타낼 수 있다.

N^((k-1)/2) * N^((k-1)/2) * N

 

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

먼저 A,B,C를 받는다.

 

def power(A, B, C):
    if B == 0:
        return 1

    tmp = power(A, B//2, C)

    if B % 2 == 1:
        return (tmp * tmp * A) % C
    else:
        return (tmp * tmp) % C

만약 지수가 0이면 1을 반환하면 된다.

 

tmp에 지수를 반으로 나눈 값을 넣어 재귀함수를 호출한다.

 

만약 지수가 홀수이면 (tmp * tmp * A) % C 식으로 나타내고

 

지수가 짝수이면 (tmp * tmp) % C 식을 나타낸다.