[C++] 백준 1629 곱셈

#include <iostream>
 
long long A = 0;
long long B = 0;
long long C = 0;
 
long long Ans(long long lCount) 
{
	if (lCount == 1)
		return A % C;
 
	long long lTemp = Ans(lCount / 2) % C;
 
	if (lCount % 2 == 0) 
		return lTemp * lTemp % C;
 
	else
		return lTemp * lTemp % C * A % C;
}
 
int main() 
{
	std::cin >> A >> B >> C;
 
	std::cout << Ans(B);
 
	return 0;
}

분할 탐색입니다.

분할 탐색임을 이해는 했지만 함수를 짜면서 횟수가 11처럼 딱 떨어지지 않는 숫자를 고려하지 않고 풀어서 틀렸었습니다.

20억번은 시간에 무조건 탈락하기 때문에 계속해서 횟수를 반으로 나누면서 풀어야 합니다.

딱 떨어지지 않는 숫자라면 한번 더 따로 곱해줘야 합니다.