**🔗 참고 문제** → [<https://www.acmicpc.net/problem/1629>](<https://www.acmicpc.net/problem/1629>)      // 클릭 시 이동

# 📌 Binary Exponentiation -> 이진 거듭제곱 / 빠른 거듭제곱

Aⁿ을 그대로 N번 곱하지 않고, 지수를 반으로 줄여가며 계산하는 방식

🔖 모듈러 성질
- (A × B) % C = ((A % C) × (B % C)) % C
- 숫자가 커지기 전에 계속 나머지 처리

🎯 문제 유형

• 지수가 매우 클 때, 거듭제곱 값 구하기

🚮 선입견을 버리자

• 단순 곱셈으로 처리하자 → ❌
  • 지수가 1억을 초과하면, 시간 초과 발생 가능
• 모듈러 연산은 마지막에 하자 → ❌
  • 곱셈 과정에서 값이 너무 커지므로, 모듈러 성질을 이용해서 매번 처리

💭 어떻게 떠올릴까

• 거듭제곱인데 지수가 클 때
  • 1억을 넘어가면 코딩테스트 제한 시간 초과 가능
• N 연산 횟수를 줄이는 방법이 뭐가 있을까?
  • N = 지수
  • 한 번 연산한 결과를 제곱해서 재사용 가능
• 지수를 1씩 줄이지 말고, 2로 나누면서 줄이자.
  • O(N) → O(logN)

📒 정리

거듭제곱 + 큰 지수 + 나머지 연산 → 이진 거듭 제곱 사용(Binary Exponentiation)