1629번 곱셈

문제링크 : www.acmicpc.net/problem/1629

1629번: 곱셈

---

---

<알고리즘>

  1) 함수를 이용하여 지수가 0혹은 1이 될때까지 반복해 2로 나누기

  2) 지수가 0이면 1, 1이면 밑을 C로 나눈 값을 return 

  3) 지수가 그 이상일 경우 홀수인지 짝수인지를 구분하여  pow 함수처럼 곱셈하여 return

 

 

메모리 : 2016KB     시간 : 0ms

#include<iostream>
using namespace std;

long long int divisionAlgo(long long int A, long long int B, long long int C) {
	if (B == 0) {
		return 1;
	}
	else if (B == 1) {
		return A%C;
	}
	long long int temp = divisionAlgo(A, (int)(B/2), C);

	//B가 짝수인 경우
	if (B % 2 == 0) {return (temp*temp) % C;}
    	//B가 홀수인 경우
	else { return (A*((temp*temp)%C)) % C; }

}
int main() {
	long long int A = 0;
	long long int B = 0;
	long long int C = 0;
	cin >> A >> B >> C;
	cout << divisionAlgo(A, B, C) << "\n";

	return 0;
}