[백준] 곱셈- python[ 구현 ]

[Silver I] 곱셈 - 1629

문제 링크

성능 요약

메모리: 31120 KB, 시간: 40 ms

분류

분할 정복을 이용한 거듭제곱, 수학

제출 일자

2023년 11월 13일 13:49:29

문제 설명

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

입력

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

출력

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

## 나의 풀이

딱 주어진 문제대로 구현할 경우의 코드이다. 시간초과가 발생한다. n 값의 범위가 2,147,483,647 이니 시간 복잡도 n 으로 풀면 안될듯 nlogn을 고민해보자

import sys

a,b,c = map(int,sys.stdin.readline().split())
answer = a
for i in range(b):
    answer *= a
    answer%= c
print(answer)

모듈러를 사용하여 기본적으로 오버헤드가 없게 코드를 작성하는 것은 생각하고 있었지만 지수의 법칙에 대해서는 생각을 못했기에 다른 사람의 풀이들을 확인해봤다. 코드는 안보고 지수 법칙을 사용한다는 개념만 확인 후 문제를 풀었다.

지수 법칙

b가 짝수일 경우 : a^b = a^(b//2) * a^(b//2)

b가 홀수인 경우 : a^b = a^(b//2) * a^(b//2) * a

지수 법칙에 대해 이해한 후 아래와 같이 작성했다.

import sys
global a, c

def check(n):
    global a, c
    if n == 1:
        return a%c 
    temp = check(n//2) % c
    if n %2 == 0:
        return temp*temp % c
    else: return a*temp*temp %c

a,b,c = map(int,sys.stdin.readline().split())

answer = check(b)
print(answer)