빠른 거듭제양 및 수론 알고리즘
빠른 거듭제곱
비트 시프트를 사용한 거듭제곱은 O(1)의 시간 복잡도를 가지지만 최대 63 제곱까지만 가능합니다. 반면, 빠른 거듭제곱 알고리즘은 O(log n)의 시간 볔잡도를 가지며 10^9 제곱까지 지원합니다. 모듈러 연산은 곱셈 단계에서 수행해야 합니다.
이 방법은 a^k mod p를 계산하는 데 사용되며, a, k, p는 각각 1e9까지 가능합니다. 이를 통해 O(log k)의 시간 ...
7월 11일 16:29에 게시됨