[ C++ ] #1629 곱셈

 

처음에는 그냥 문제 그대로 a를 b번 곱해준 뒤 c로 나눠서 출력해줬다.

이렇게 쉬울리가 없는데 하면서 실행시켜보니 음수값이 나왔다...

 

코드를 보면 음수값이 나올 이유가 전혀 없었는데...곰곰히 생각해보니 overflow가 일어났다는 것을 알 수 있었다. 

그래서 곱해주는 것과 동시에 C로 계속 나눠주었다.

 하지만 이렇게 하니 A,B,C가 커질수로 시간이 너무 오래 걸렸다. 

 

이 문제의 핵심은 재귀이다

결국 a의 b승을 c로 나눴을 때 나머지를 구하는 것이다.

b가 짝수이면 : a^b = a^(b/2) x a^(b/2)
b가 홀수이면 : a^b = a^(b/2) x a^(b/2 + 1)

위 식을 이용하여 분할정복 해야한다. 

 

분명 맞는데...왜 자꾸 틀리지 했더니

곱셈과정에서 int의 범위를 넘어가는 것 같아서 long long으로 고쳤더니 맞았다!

 

#include <iostream>

using namespace std;

long long  A, B, C;

long long p(long long b) {
	if (b == 0) return 1;
	if (b == 1) return A%C;

	long long k = p(b / 2)%C;
	if (b % 2 == 0) return k * k%C;
	else return (k* k%C)*(A % C);
}

int main() {

	cin >> A >> B >> C;
	
	cout << p(B)%C;
}