문제

코드

import sys
input = sys.stdin.readline

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

def divCon(a,b):
    if b==1:
        return a%c 
    else:
        div = divCon(a,b//2)

        if b%2==0: #짝수 
            return div*div%c 
        else : #홀수 
            return div*div*a%c 

print(divCon(a,b))

해설

후,,. 그냥 단순히 제곱을 계산하고 나머지 연산을 진행하면 당연빠따로 시간초과가 걸리게된다.
이 문제를 위해서 알아야하는 개념은 내가 보기엔 두가지이다!

첫번째 개념

제곱을 구하는 분할정복 개념이다

이와같이 거듭제곱은 반씩 나눠서 계산하는 방법을 가져야 한다.
이렇게 한다면 그냥 거듭제곱을 무작정 구하는것보다 시간복잡도를 엄청나게 줄일 수 있다.
기존의 제곱해서 구해야하는 알고리즘의 시간복잡도는 O(n)인 반면 분할정복을 거치면 O(log n)이므로 훨씬 빨라진다 !
이를 구현한 코드가 아래의 코드이다.

def divCon(a,b):
    if b==1:
        return a%c 
    else:
        div = divCon(a,b//2)

    if b%2==0: #짝수 
        return div*div%c 
    else : #홀수 
        return div*div*a%c 

그런데... 왜 return 할때마다 나머지 연산자를 해주니 의아할 수 있다.
그 이유는 바로 다음 개념에 있다.
### 나머지 연산자의 분배법칙
> ![](https://velog.velcdn.com/images%2Fseochan99%2Fpost%2F591713a0-5bff-41f2-a529-2f8d53d0c60a%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202021-10-03%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%205.19.27.png)
이런 방식으로 각각 나머지 연산을 해주고 마지막에 한번 더 해줘야한다..
몰랐다... 인생 23년 살면서 나머지 연산자의 분배법칙을 이제야 알았다니 대박..
그런데..! 이런 나머지 연산자의 분배법칙이 적용되지 않는 특이케이스가 있다.
바로 나눗셈에 대한 나머지 연산은 분배법칙이 적용되지 않기에 이를 위해서는 페르마의 소정리를 이용해서 분모를 분자로 올려야한다.
이에 대한 설명은 추후에 문제에 나오면 설명하겠다.

# 덧붙여서
> 문제의 난이도가 올라갈수록 배울 수 있는 부분이 점점 많아지고 몰랐던 부분도 점점 많아져 빈틈을 찾는거 같아 기분이 좋다..
물론... 하나하나 푸는데 주옥같지만말이닷...! 아직 실버1인데 큰일났당..케케