[백준/BOJ] 1629 - 곱셈 (c++) (분할정복)

1. 문제

www.acmicpc.net/problem/1629

---

2. 풀이

A의 B승은 A의 B/2승의 제곱과 같다.

 

 

 

위와 같이 지수가 짝수일 경우 단지 지수를 반으로 쪼개기만 하면 되었지만

 

아래의 수식과 같이 지수가 홀수일 경우 반으로 쪼개는 것과 동시에 밑을 하나 더 곱해주면 된다.

 

---

3. 소스코드

#include <stdio.h>

typedef long long ll;

int a, b, c;

ll power(long long n, long long m) {
	if (m == 0) return 1;
	ll res = power(n, m / 2) * power(n, m / 2) % c;
	if (m % 2) return res * n % c;
	return res;
}

int main() {
	scanf("%d %d %d", &a, &b, &c);
	printf("%lld", power(a, b));
}

---

4. 참고

---

질문, 고칠점 등 댓글 언제나 환영입니다.