코딩테스트/파이썬
백준 1629번 곱셈
도리닥
2021. 1. 28. 22:01
728x90
문제 설명
문제를 분석해보면 A의 B제곱을 C로 나눈 나머지는 A의 B/2제곱을 C로 나눈 나머지를 알면 알 수 있다. 이 뜻은 K제곱을 계산했으면 2K제곱과 2K+1제곱을 계산할 수 있다는 뜻이다. 그래서 B가 1이면 A % C를 리턴하고 그렇지 않으면 B를 2로 나눈 값을 인자로 넣어 재귀함수를 실행한다.
전체 코드
def func(a,b,c):
if b == 1:
return a % c
val = func(a,b//2,c)
val = val * val % c
if b % 2 == 0:
return val
else:
return val * a % c
def main():
li = list(map(int,input().split()))
print(func(li[0],li[1],li[2]))
728x90
반응형