[C++] 백준 1629번 : 곱셉

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

1629번: 곱셈

---

 문제 풀이

브루트 포스로 문제를 풀게 되면 절대 시간 초과가 발생하는 문제이다.

문제를 풀기 위해선 아이디어가 절대적으로 필요하다.

나머지 연산은 분배법칙이 성립한다. 즉, A × B % C = (A % C × B % C) % C 이 성립한다.

함수 pow는 b가 홀수인지 짝수인지에 따라서 연산이 다르다.

b가 홀수인 경우는 a를 한 번 더 곱하고 나머지 연산을 한 번 더 해준다.

왜냐하면 a^10은 a^5 × a^5로 한번 더 연산을 할 필요가 없지만 

a^5는 a^2 × a^2 × a로 a가 하나 남아 추가적으로 연산을 진행해주어야 한다. 

 느낀 점 

처음에는 전혀 다른 방식으로 접근했다. 나머지가 되는 숫자는 일정하게 반복될 것이라고 생각하고 재귀를 통해서 반복되는 숫자를 벡터에 집어넣고 b값을 나머지 연산을 통해서 출력하게 했으나 21억이 되는 값에 대해서 시간 초과가 발생해버렸다. 나머지 연산이 분배 법칙이 성립한다는 것을 알고도 이해하지 못했으나 직접 쓰면서 풀어보곤 이해했다. 수학적인 사고가 확실히 부족한 것 같다.

 코드

#include <iostream>

using namespace std;

int a, b, c;

long long pow(int a, int b, int c) {
	if (b == 0) return 1;
	long long tmp = pow(a, b / 2, c);
	tmp = tmp * tmp % c;
	if (b % 2 == 0) return tmp;
	else return (tmp * a) % c;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> a >> b >> c;
	cout << pow(a, b, c);
}