BOJ (C/C++) 1629번: 곱셈

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

1629번: 곱셈

---

풀이

반복문을 이용한 계산은 시간초과가 발생해서, 알고리즘 설명대로 분할 정복을 이용한 거듭제곱으로 계산했다.이 과정에서 A는 int형의 범위가 넘어갈 수 있으므로 long long 으로 지정해줬다.(백준에서는 long long형 변수를 %d로 입력받아도 오류가 안 나는데 VS 환경에서는 발생함.)

---

코드

#include <stdio.h>
int main() {
	int B, C;
	long long int A, sum = 1;

	scanf("%lld %d %d", &A, &B, &C);
	while (B) {
		if (B & 1) sum = (sum* A) % C;
		A = (A*A) % C;
		B >>= 1;
	}

	printf("%lld", sum);
	return 0;
}