백준 1629번: 곱셈

www.acmicpc.net/problem/1629

1629번: 곱셈

---

구하는 것이 이전 글과 같습니다.

 

2021/01/23 - [분할 정복을 이용한 거듭제곱/정수 거듭제곱] - 백준 13171번: A

백준 13171번: A

 

저는 A, B, C의 범위가 최대 2,147,483,647이라는 점을 고려하여,

 

int범위에서 power_modular, multiply_modular를 구현하려고 했습니다.

 

그 결과 add_modular함수까지 필요하게 되었는데,

 

코딩 분량을 줄이기 위해서 long long 범위에서 power_modular 함수만 구현해도 좋을 것 같습니다.

 

#include <stdio.h>

int add_modular (int a, int b, int M);
int multiply_modular (int a, int b, int M);
int power_modular (int a, int b, int M);

int main() {

	int A, B, C;
	scanf("%d %d %d", &A, &B, &C);
    
	printf("%d", power_modular(A, B, C));
    
	return 0;
}

int add_modular (int a, int b, int M) {
	a %= M;
	b %= M;
	if (a >= M - b) {
		return a - (M - b);
	}
	else {
		return a + b;
	}
}

int multiply_modular (int a, int b, int M) {
	a %= M;
	b %= M;
	int result = 0;
	while (b > 0) {
		if (b & 1) {
			result = add_modular (result, a, M);
		}
		a = add_modular (a, a, M);
		b >>= 1;
	}
	return result;
}

int power_modular (int a, int b, int M) {
	a %= M;
	int result = 1;
	while (b > 0) {
		if (b & 1) {
			result = multiply_modular (result, a, M);
		}
		a = multiply_modular (a, a, M);
		b >>= 1;
	}
	return result;
}

 

C11 코드, 1116KB, 0ms 입니다. (제출 번호 25534367)

---

이번에는 add_modular함수를 기존 블로그 글에서 약간 바꿨지만, 큰 차이는 없습니다.

 

또 이번 문제는 이전에 다뤘던 13171번과 문제가 거의 같습니다. 

 

그런데 실버4 티어인 13171과 비교하면 티어가 꽤나 높은데,

 

13171번의 경우 본문에 풀이가 거의 그대로 나와있던 게 원인인 것 같습니다.