백준 1629 곱셈 c++ // 재귀함수

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

1629번: 곱셈

1. 최대한 예시에서 일반식을 도출하라.

ex) a^4%c = a^2%c * a^2 %c

-> a^b%c = a^b%c * a^b %c

ex) a^5%c = a^2%c * a^2 %c * a^1 %c

-> a^b%c = a^b%c * a^b %c * a^1 %c

 

2. (공통부분을) 먼저계산 후 리턴하면된다.

 

#include <bits/stdc++.h>
using namespace std;

int a, b, c;

using ll = long long;

//함수정의 : a^b를 c로나눈 나머지 리턴
ll go(ll a, ll b, ll c) {
	//기저사례 : b==1
	if (b == 1) {
		return a % c;
	}

	//재귀식
	//ex) a^4%c == a^2%c * a^2%c
	//a^5%c == a^2%c * a^2%c * a%c
	//a^2%c * a^2%c 이부분을 val로 미리 계산한다!

	ll val = go(a, b / 2, c);
	val = val * val % c;

	
	if (b % 2 == 0) {
		return val;
	}
	else {
		return val*a%c;
	}


}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> a >> b >> c;

	cout<<go(a, b, c);
}