GitHub

https://github.com/Choidongjun0830

파이썬 알고리즘 문제 풀이

Baekjoon Online Judge 1629번 파이썬. 분할 정복.

gogi masidda 2022. 12. 29. 17:28

문제 링크
https://www.acmicpc.net/problem/1629

1629번: 곱셈

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

www.acmicpc.net


A^(m+n) = A^m * A^n
(A*B)%C = (A%C)*(B%C)%C
위의 지수법칙. 분배 법칙을 알아두어야 한다.

정답 코드

A,B,C = map(int,input().split())

def solution(a,b,c):
  if b == 1: #a의 1제곱이면.
    return a%c
  N = solution(a,b//2,c) # a^(b//2) 구하기
  if b % 2 == 0: #b가 짝수
    return N*N%c #지수 법칙 사용
  else: #b가 홀수
    return N*N*a%c #지수 법칙 사용
    
print(solution(A,B,C))
728x90