[BOJ 12728 // C++] n제곱 계산

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 12728번 문제인 n제곱 계산이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/12728

12728번: n제곱 계산

이 문제에서 주의해야할 점은 단순히 거듭제곱만 하면 지수가 커질 수록 실수부에서 오차가 크게 발생하게 된다는 것이다. 따라서, 단순히 빠르게 계산하는 것만 고려할 것이 아닌 실수오차가 나지 않게 정수만으로 해결할 방법을 찾는 것이 좋다.

 

문제집에 종종 나오는 문제풀이 트릭을 떠올려보자.

3-sqrt(5)<1 을 만족하는 것은 분명하고, X = (3+sqrt(5))^n + (3-sqrt(5))^n 이 정수임을 보이는 것은 이항정리(binomial theorem)을 이용하면 간단히 보일 수 있다.

따라서 (3+sqrt(5))^n의 정수값은 X에서 1을 뺀 값임을 알 수 있다.

또한, (3+sqrt(5))^n을 a+b*sqrt(5) 로 표현할 때, X = 2*a임도 알 수 있다.

 

따라서 남은 것은 (3+sqrt(5))^n = a+b*sqrt(5)를 만족하는 a와 b를 빠르게 찾는 것이다.

이는 관계식을 행렬로 작성한 뒤 binary exponentiation을 이용하면 빠르게 해결 가능하다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

int main()
{
    int T; cin >> T;
    long long N;
    for (int t = 1;t <= T;t++) {
        cin >> N;
        int mat[2][2] = { {3,5},{1,3} };
        int res[2] = { 1,0 };
        while (N > 0) {
            if (N & 1) {
                int temp[2] = { mat[0][0] * res[0] + mat[0][1] * res[1],mat[1][0] * res[0] + mat[1][1] * res[1] };
                res[0] = temp[0] % 1000; res[1] = temp[1] % 1000;
            }
            int temp[2][2] = { {mat[0][0] * mat[0][0] + mat[0][1] * mat[1][0],mat[0][0] * mat[0][1] + mat[0][1] * mat[1][1]},
                {mat[1][0] * mat[0][0] + mat[1][1] * mat[1][0],mat[1][0] * mat[0][1] + mat[1][1] * mat[1][1]} };
            mat[0][0] = temp[0][0] % 1000; mat[0][1] = temp[0][1] % 1000; mat[1][0] = temp[1][0] % 1000; mat[1][1] = temp[1][1] % 1000;
            N >>= 1;
        }
        int ans = (res[0] * 2 - 1)%1000;
        if (ans < 10) {
            cout << "Case #" << t << ": 00" << ans << '\n';
        }
        else if (ans < 100) {
            cout << "Case #" << t << ": 0" << ans << '\n';
        }
        else {
            cout << "Case #" << t << ": " << ans << '\n';
        }
    }
    return 0;
}