[C++] 1629 : 곱셈

실버 Ⅰ

 

#include <iostream>

using namespace std;

int pow(int a, int b, int c) {
	if (b == 0) return 1;

	long long n = pow(a, b / 2, c);
	long long nn = n * n % c;
	if (b % 2) {
		return nn * a % c;
	}
	else {
		return nn % c;
	}
}

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

 

분할 정복을 이용한 거듭제곱

문제 - 1 페이지

 

pow 함수가 int형이라 return값이 int를 넘어가는지 안넘어가는지 조심해야 했다

사실 longlong으로 해도 되지만 오기가 생겨서 int로 함

 

애초에 %c를 적절히 해주면 절대 리턴값이 int형을 벗어나지 않을거라고 생각해서..

근데 (a*b)%c == (a%c)*(a%c) 를 은근히 어디다가 써야할 지 헷갈렸다

 

이 형태 그대로 유지해서 쓰려면 %c를 너무 남발해야 하는 것 같기도 하고 그랬는데

어차피 리턴값만 int를 안 넘으면 되니까 마지막에 %c정도 해줬다

 

c가 int니까 %c 한 값 도한 int범위 내에 있다