C++ 백준_1629_"곱셈"

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

1629번: 곱셈

 

A^4

인 경우

(A * A) ^ 2 가 된다

즉 (A*A)한 것을 또 A*A 할 필요가 없다

​

반으로 나누면서 계산된 것은 다시 반복을 제외시킴으로

시간을 단축한다.

​

단, 계산 중간에 C로 나눈 나머지를 해야하는데

C 보다 큰 경우 나머지를 구해야지,

무조건 하다 보면

나머지가 0인 경우를 잘못반환하게 될 수 있다

그럼 나머지 계산은 다 0이 되므로 주위한다.

#include <iostream>
using namespace std;


int half_mult(long long A,long long B,long long C) {

	if (B == 1) {
		return A;
	}

	long long mult = half_mult(A, B / 2, C);
	
	if (mult > C)
		mult %= C;

	long long result = (mult * mult)%C;
	
	if (B % 2 != 0) {
		result *= A;
		if (result > C) {
			result %= C;
		}
	}
	return result;
}


int main(void) {

	long long A, B, C;

	cin >> A >> B >> C;

	cout << half_mult(A, B, C)%C;

}