43. Power by Divide and Conquer

정수론 문제를 풀기 위해서 알아 두어야 하는 두 가지 기본적인 지식이 존재하는데, 분할 정복을 이용한 거듭제곱과 유클리드 호제법이 그것이다.

 

분할 정복을 이용한 거듭제곱(Power by Divide and Conquer)의 기본적인 원리는 이 글에서 설명한 적이 있다. 거듭제곱 $x^y$를 구하는 두 가지 방법을 요약하면 다음과 같다.

• $y$를 $2$의 거듭제곱의 합으로 나타낸 다음 $x$를 제곱해 나가면서 곱을 구한다.
• $y$가 홀수인 경우 $x^{y-1}$과 $x$를 곱해서 답을 구하고, $y$가 짝수인 경우 $x^{y/2}$를 제곱해서 답을 구한다.

두 가지 방법의 구현은 다음과 같다. 일반적인 경우 답이 커지는 것을 피하기 위해 어떤 수 $p$로 나눈 나머지를 대신 구하게 되는 경우가 많기 때문에 코드도 그렇게 작성되어 있다.

------------------------------------------------------------

typedef long long LL;
LL pow(LL x, LL y, LL p)
{
    LL s = 1;
    for(; y; y >>= 1)
    {
        if(y & 1)s = s * x % p;
        x = x * x % p;
    }
    return s;
}

------------------------------------------------------------

typedef long long LL;
LL pow(LL x, LL y, LL p)
{
    if(y == 0)return 1;
    else if(y & 1)return pow(x, y - 1) * x % p;
    else
    {
        LL t = pow(x, y / 2, p);
        return t * t % p;
    }
}

------------------------------------------------------------

두 번째 코드는 다음과 같이 else 키워드를 빼고 조금 더 짧게 작성할 수도 있다.

typedef long long LL;
LL pow(LL x, LL y, LL p)
{
    if(y == 0)return 1;
    if(y & 1)return pow(x, y - 1) * x % p;
    LL t = pow(x, y / 2, p);
    return t * t % p;
}

분할 정복을 이용한 거듭제곱은 조합이나 모듈러 곱셈 역원을 구할 때 사용되기 때문에 잘 알고 있어야 한다.

 

[연습문제]

 

BOJ 13171. A (Silver IV)

거듭제곱을 구하는 두 번째 방법이 문제에 설명되어 있다. 단 밑이 $10^{18}$까지 커질 수 있으므로 바로 계산하려면 $16$바이트 정수 자료형을 사용해야 한다. 하지만 $A$를 $10$억 $7$로 나눈 나머지를 $A$ 대신 사용하면 $8$바이트 정수 자료형을 사용해서 풀 수 있다.

 

→ solved.ac tag: exponentiation_by_squaring