파이썬 곱셈(백준 BOJ 1629)
2023, Apr 01
파이썬 곱셈(백준 BOJ 1629)
문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
예제 입력 1
10 11 12
예제 출력 1
4
📝 풀어보기
분할정복을 사용한 제곱
우리는 A^8이 있다면 원래 A*A*A*A*A*A*A*A 으로 곱셉 7번을 할것이다.
하지만 ((A^2)^2)^2를 한다면 7번의 연산을 3번으로 줄일 수 있다.
이 연산법은 다음과 같다.
A^4 = (A^2)^2 (짝수일때)
A^5 = A * A^4 = A * (A^2)^2 (홀수일때)
import sys
input = sys.stdin.readline
A, B, C = map(int, input().split())
def fpow(A, B):
# 제곱 하는 횟수가 1이면
if B == 1:
# A % C 반환
return A % C
# 제곱 하는 횟수가 1 이상일 때
else:
# A와 B를 반으로 나눈 몪을 함수 호출
x = fpow(A, B//2) # ex) 10 11 12 경우 10 100 10000
if B % 2 == 0:
return (x * x) % C # 100
else:
return (x * x * A) % C # 100000, 100000000000
print(fpow(A, B))