[백준] 1629번 곱셈

www.acmicpc.net/problem/1629

1629번: 곱셈

구현 자체는 어렵지 않은데 방식을 모르면 쉽게 풀 수 없는 문제 같다.

여러 번 풀면서 방식을 익혀놓으면 다른 문제 풀 때 사고에 도움이 될 것 같다.

 

알고리즘 방식

 

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <list>
#include <stack>
#include <deque>

using namespace std;

long long pow(long long a, long long b, long long c) {
	if (b == 1)
		return a % c;
	
	long long val = pow(a, b / 2, c);
	val = val * val % c;
	if (b % 2 == 0)
		return val;
	else
		return val * a % c;

}

int main(void) {
	long long A, B, C;
	long long result = 1;
	cin >> A >> B >> C;

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