거듭 제곱 구하기 - 분할 정복 방법

아래의 내용을 먼저 보고 오는 것도 좋다.

designatedroom87.tistory.com/47?category=868275

거듭 제곱 구하기 - basic

 

1. 설명

위의 점화식에서, n이 홀수일 때의 []기호는 가우스 기호이다.

 

위의 식에 n을 8이라고 두면

위의 식에서, n = 8일 때의 값을 구하려면,

C의 제곱을 먼저 구한 뒤에 두 번 더 반복해서 제곱을 하면

된다. 결국, 3번의 곱셈을 하면 된다.

 

n이 만약에 홀수라면 (예를 들어 n을 9라고 가정하면 )

위에서 구한 n = 8일 때의 값에서 C를 한번만 곱해주면 된다.

 

2. 구현

프로그램 실행결과

3. 소스 파일

main.c

0.00MB