백준 1629번 곱셈 C++

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

 

분할 정복을 이용하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int64 solve(int64 a, int64 b, int64 c) {
	if (b == 1)
		return a % c;

	int64 tmp = solve(a, b / 2, c);
	if (b % 2 == 0)
		return tmp * tmp % c;
	return ((tmp * tmp) % c * a) % c;
}

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

	int64 a, b, c;
	cin >> a >> b >> c;
	cout << solve(a, b, c);
};