(pow(A,B))mod C 를 logB 시간안에 구하는 함수

http://jason9319.tistory.com/169

예전에 이항 계수를 구할 때 설명한 적이 있지만 빈번하게 사용되는 유용한 테크닉이라 생각되어 다시 설명드립니다.

우선 소스코드를 먼저 보시죠

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a, b, c;
ll mypow(ll x, ll y) {
    if (!y)return 1;
    if (y % 2)
        return (x*mypow(x, y - 1)) % c;
    return mypow((x * x) % c, y / 2) % c;
}
int main() {
    scanf("%lld%lld%lld", &a, &b, &c);
    printf("%lld", mypow(a, b));
    return 0;
}

다음 소스코드는 BOJ 1629 곱셈 정답 소스코드입니다.

재귀 호출되는 과정을 보면 y가 홀수일 때는 brute force와 같은 직접 곱해주는 방법을 사용합니다.

하지만 y가 짝수일 때 y를 2로 나누어주면서 x를 제곱한 수를 호출합니다.

이와같은 분할정복으로 pow(a,b)를 logb 시간에 해결해줄 수 있습니다.