🖋️ 문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
🤔 접근
hpec에서 제곱수에 대한 나머지 연산 관련 문제가 있었던 것 같다. 그때 공부했었는데 기억이 잘 나지 않아서 검색을 해봤는데 파이썬에서 제공하는 함수로 한방에 처리가 되었다...
a, b, c = map(int, input().split())
print(pow(a, b, c))그래도 분할정복이 무엇인지는 다시 짚어보고 가야할 것 같아서 함수 구현도 해 보았다.
💻 내 코드
def power(a, b, c):
if b == 0:
return 1
elif b%2 == 0: # 짝수인 경우
half_pow = power(a, b//2, c)
return (half_pow * half_pow) % c
else:
half_pow = power(a, (b-1) // 2, c)
return (a * half_pow * half_pow) % c
a, b, c = map(int, input().split())
print(power(a, b, c))👍 제출
