Power by Divide and Conquer (1) 썸네일형 리스트형 43. Power by Divide and Conquer 정수론 문제를 풀기 위해서 알아 두어야 하는 두 가지 기본적인 지식이 존재하는데, 분할 정복을 이용한 거듭제곱과 유클리드 호제법이 그것이다. 분할 정복을 이용한 거듭제곱(Power by Divide and Conquer)의 기본적인 원리는 이 글에서 설명한 적이 있다. 거듭제곱 $x^y$를 구하는 두 가지 방법을 요약하면 다음과 같다. $y$를 $2$의 거듭제곱의 합으로 나타낸 다음 $x$를 제곱해 나가면서 곱을 구한다. $y$가 홀수인 경우 $x^{y-1}$과 $x$를 곱해서 답을 구하고, $y$가 짝수인 경우 $x^{y/2}$를 제곱해서 답을 구한다. 두 가지 방법의 구현은 다음과 같다. 일반적인 경우 답이 커지는 것을 피하기 위해 어떤 수 $p$로 나눈 나머지를 대신 구하게 되는 경우가 많기 때문에.. 이전 1 다음
