알고리즘 및 코딩/[코딩 연습] 백준,프로그래머스 파이썬 답안 💻

[백준] 1629번: 곱셈

kks2 2023. 5. 6. 20:19
728x90

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

 

1629번: 곱셈

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

www.acmicpc.net

단계: 실버1

알고리즘 분류: 

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

 

python 파이썬 답압:

# 곱셈 - 분할 정복
import math


def squere(a,b,c):
    # print(a,b)
    if b ==1:
        # print("hi")
        return a%c
    elif b%2==0:
        a = (squere(a,b//2,c)**2)%c
    elif b>=3: 
        a = (a%c*(squere(a, b//2,c)**2))%c
    return a%c
a,b,c = map (int, input().split())

print(squere(a,b,c))
728x90