Archive
Binary Exponentiation
Binary Exponentiation(exponentiation by squaring)은 a의 n제곱을 O(n) 대신 O(logn) 의 곱셈만 사용하여 계산할 수 있는 트릭이다. 이 트릭은 수리적인 일 이외의 다양한 분야에 적용할 수 있고, 때문에 결합법칙을 갖는 모든 연산에 사용될 수 있다. 알고리즘 a의 n제곱은 단순히 a에 a를 n-1번 만큼 곱해주는 것으로 표현할 수 있다. 하지만 이런 방식은 a나 n이 큰 경우 효율적이지 못하다. Binary Exponentiation의 핵심은, 제곱수 n의 이진표현이다. 다음은 n을 이진수로 변경을 한 예시이다. 적용 기존의 재귀 방식으로 제곱을 계산하는 코드. long long binpow(long long a, long long b) { if (b == ..
