백준 1629번 곱셈

문제

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.

출력

첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.

 

분할 정복으로 풀 것.

2의 배수 제곱은 1~2의 배수까지 가지 말고 2의 배수 / 2 제곱 만큼만 구한 뒤 그것을 곱해주면

시간이 반으로 줄어든다.

 

 

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
long long A, B, C;

long long cal(long long A, long long B)
{
	if (B == 1)
	{
		return A;
	}
	else if(B == 0)
	{
		return 1;
	}
	else
	{
		if (B % 2)
		{
			return cal(A, B - 1) * A % C;
		}
		else
		{
			long long half = cal(A, B / 2);
			return half * half % C;
		}
	}
}


int main(int argc, char** argv)
{
	cin >> A >> B >> C;
	
	cout << cal(A,B) % C << endl;
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}