BOJ 1629, 곱셈
ProblemSolving ·이 문제는 분할정복 문제입니다.
풀이
지수 b를 0이 될 때까지 반씩 나눠줍니다. b가 홀수라면 a를 한번 곱해줍니다.
반씩 나눠졌던 값들이 서로 곱해지면서 최종적으로 a의 b제곱의 값을 c로 나눈값 구해냅니다.
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
ll pow(ll a, ll b, ll c)
{
if (b == 0) return 1;
ll temp = pow(a, b / 2, c);
ll sum = temp * temp %c;
if (b % 2 == 1) sum = a * sum %c;
return sum;
}
int main()
{
ll a, b, c;
cin >> a >> b >> c;
printf("%lld\n", pow(a, b, c));
return 0;
}