[백준 / BOJ] C++ 1629 곱셈

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

1629번: 곱셈

풀이

간단하지만 수의 크기때문에 생각의 시간이 필요했던 문제.

 

(A * B) % C = (A%C * B%C) %C 

 

위처럼 생각하여 C로 나누어 주어 숫자를 줄여 풀이가 가능하다.

 

Code ( C++ )

#include <iostream>

using namespace std;


long long pow(long long A, long long B, long long C)
{
	if (B == 0) 
		return 1;
	if (B == 1)
		return A % C;
	long long result = pow(A, B / 2, C);
	
	result = result * result % C;
	if (B % 2 == 0)
		return result;
	return result * A % C;
}

int main()
{
	long long A, B, C;

	cin >> A >> B >> C;

	cout << pow(A, B, C);
}