백준 1629(곱셈)

#include<iostream>
using namespace std;
#define MAX 31


int A, B, C, tmp = 1024*1024*1024, result = 1;
int how_m[MAX];
bool check2 = false;
bool check[MAX] = { false };

int main() {
	cin >> A >> B >> C;
	how_m[0] = A%C;
	for (int i = 1; i < MAX; i++) {
		how_m[i] = (how_m[i - 1] * how_m[i-1])%C;
	}
	for (int i = 30; i >= 0; i--) {
		if (B >= tmp) {
			B -= tmp;
			check[i] = true;
		}
		tmp /= 2;
	}
	for (int i = 0; i < MAX; i++) {
		if (check[i]) {
			check2 = true;
			result = (result * how_m[i]) % C;
		}
	}
	if (check2) {
		cout << result << "\n";
	}
	else {
		cout << 0 << "\n";
	}
}

큰 수의 곱셈에 대한 나머지 계산을 해봤었기 때문에 바로 곱셈에 대한 나머지 성질로 분할 계산 생각을 할 수 있었다.

 

(A^B)%C를 구하고자 할 때 B를 2^2이라고 하면

 

(A^2) %C의 값은 ((A%C) * (A%C)) % C 로 계산할 수 있다.

 

B가 2^5이라면 

 

(A^3)%C 꼴을 ((A^2)%C * (A%C))%C꼴로 나타낼 수 있고, B의 값을 합꼴로 나타내서 그 값을 구해놓은뒤 연산을 편리하게 할 수 있다. 

 

예를 들어서 B = 5인 경우 B = 2+2+1로 할 수 있다. 

하지만 이처럼 사람의 뇌를 거친 분할을 컴퓨터 코드에 저장하긴 힘드므로 규칙을 만들어서 B의 값을 찾는다.

 

B의 값을 이진수로 만들어서 계산을 한다. 

이처럼 이진수로 계산을 한다면 총 31번의 연산으로 B = 2^31-1 까지 필요한 값을 저장해놓을 수 있다.

 

for (int i = 1; i < MAX; i++) {
how_m[i] = (how_m[i - 1] * how_m[i-1])%C;
}

이 코드로 미리 값들을 저장해놓은 뒤 

 

for (int i = 30; i >= 0; i--) {
if (B >= tmp) {
B -= tmp;
check[i] = true;
}
tmp /= 2;
}

이 코드로 B번 연산하기 위해서 필요한 2의 거듭제곱 수들을 확인한다. 

 

 

위 코드가 전체적인 짜임이었고, 특별케이스를 확인해본다. 

 

문제 조건에서 A, B, C가 모두 signed int 값이므로 경계값에서 연산을 하였을 때 int값의 범위를 초과하는 것을 확인할 수 있다. 따라서 최악의 값이 생성될 수 있는 A^2정도 이상의 자료형이 필요하다.

 

또한 코드를 처음 구성할 때 단순 result 값을 출력을 했었는데 이 경우에는 모든 비트가 0일 경우 코드에서는 bool check[i]의 모든 값들이 0인 경우에도 result의 초기값이 1이므로 1을 출력하는 경우가 발생해서 bool check2도 만들어서 확인 하였다.