거듭제곱(pow)연산 구현

의 값을 구하기 위한 거듭제곱 연산을 구현한다고 하자.

naive한 방법은 for문을 돌면서 N을 K번 곱해주면 된다. 이럴 경우 시간복잡도는 O(K)이다.

int result=1;
for(int i=1 ; i<=k ; i++)
    result=result*n;

하지만 O(K)보다 빠른 O(logK)만에 구하는 방법도 존재한다. 바로 N^2을 이용하여 N^4를 구하고, 또 이를 이용하여 N^8을 구하는 방식 이용해서 말이다. 

typedef long long ll;
ll my_pow(ll n,ll k){
    ll result=1;
    while(k){
        if(k&1) //k값이 홀수일 때만 계산
            result=result*n;
        k/=2;
        n=n*n;
    }
    return result;
}
 

나머지를 취해야할 때는 이렇게 하면 된다.

typedef long long ll;
ll my_pow(ll n,ll k){
    ll result=1;
    while(k){
        if(k&1) //k값이 홀수일 때만 계산
            result=(result*n)%MOD;
        k/=2;
        n=(n*n)%mod;
    }
    return result;
}

또한 (나머지 거듭제곱)-(나머지 거듭제곱)을 필요로 하는 경우가 있다. 이때 주의해야할 점은 나머지를 취했기 때문에 음수가 나올 수도 있다는 점이다. 이를 방지하기 위해서는 마지막에 MOD를 더해주고, 다시 MOD를 나머지 취해주어야 한다.

typedef long long ll;
ll my_pow(ll n,ll k){
    ll result=1;
    while(k){
        if(k&1) //k값이 홀수일 때만 계산
            result=(result*n)%MOD;
        k/=2;
        n=(n*n)%mod;
    }
    return result;
}
int main(){
 
    int ans=0;
    ans-=my_pow(N,K);
 
    ans=ans+MOD;
    ans=ans%MOD;
    
    .
    .
    .
}