[백준/파이썬/수학] 1629번 곱셈 코딩테스트 연습풀이 실버1

문제 출처: https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

 

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

예제 입력 1

10 11 12

 

예제 출력 1

4

 

정답

def power(a, b):
    if b == 1:
        return a % C
    else:
        tmp = power(a, b // 2)
        if b % 2 == 0:
            return tmp * tmp % C
        else:
            return tmp * tmp * a % C


if __name__ == "__main__":
    A, B, C = map(int, input().split())

    result = power(A, B)
    print(result)

b의 값이 짝수인지 홀수인지 파악을 먼저한 후 b의 값이 짝수라면 10 ^10 -> (10^5)^2 형태로 바꿔주고 b의 값이 홀수라면 10 ^11 -> (10^5)^2 * 10 형태로 바꿔주는 방식으로 진행합니다.

 

이번 문제는 좀 어려웠던 것 같습니다!