[백준/파이썬] 1629번 곱셈 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1629번 곱셈
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

A^B mod C를 계산하는 문제입니다.

지수가 매우 크므로 단순 반복 곱셈 대신 빠른 거듭제곱(분할 정복)을 사용해야 합니다.

코드

a, b, c = map(int, input().split())

def power(a, b, c):
    if b==1:
        return a%c
    elif b%2==0:
        tmp = power(a, b//2, c)
        return (tmp%c*tmp)%c
    else:
        tmp = power(a, (b-1)//2, c)
        return ((tmp%c*tmp)%c*a)%c
print(power(a%c,b,c))

설명

지수를 절반씩 줄여 재귀 호출합니다.

• b가 짝수면 (a^(b/2))^2
• b가 홀수면 (a^((b-1)/2))^2 * a

각 단계에서 % c를 적용해 수 크기를 제한합니다.

---

• 백준 문제풀이 전체 목록 보기

---