백준 1629번 곱셈

문제 설명

 

 

 

문제를 분석해보면 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]))