[C] 백준 1629번 곱셈

링크
https://www.acmicpc.net/problem/1629

문제

---

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

---

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

예제 입력 1

---

10 11 12

예제 출력 1

---

4

아이디어 스케치

---

분할 정복 알고리즘을 사용하지 않을 경우 시간 초과가 발생한다.

분할 정복 알고리즘을 사용하여 거듭제곱을 계산하기 위해서는 다음과 같은 아이디어가 필요하다.

$C^n$은 위 식과 같이 분할할 수 있다.

즉 n이 1일 때는 자기 자신을 return하고, n이 짝수일 때는 두 번째 식을 return하고, n이 홀수일 때는 세 번째 식을 return하는 재귀함수를 구현하면 된다.

전체 코드

---

#include <stdio.h>

#define lld long long 

int divide_pow(int a, int b, int c);

int main()
{
	int A, B, C;

	scanf("%d %d %d", &A, &B, &C);

	printf("%lld", divide_pow(A % C, B, C));

	return 0;


}

int divide_pow(int a, int b, int c) {
	lld tmp;
	if (b == 1)	// 어떤 수의 1제곱은 자기 자신
		return a;
	else {
		tmp = divide_pow(a, b / 2, c);
		if (b % 2 == 0)
			return (tmp * tmp)%c;		
		else
			return ((tmp * tmp)%c * a) % c;
	}
}

제출 결과

---