백준 11778번 피보나치 수와 최대공약수

문제 링크입니다: https://www.acmicpc.net/problem/11778

N, M이 매우 크기 때문에 시간복잡도 O(N)으로는 어림도 없는 문제였습니다.

https://jaimemin.tistory.com/324?category=987849 이 문제를 보면 행렬의 곱셈을 통해 피보나치 수열을 구할 수 있는 것을 알 수 있습니다.

따라서, 분할정복을 이용해 행렬의 N승을 빨리 구하는 것이 핵심이였습니다.

이 때, 행렬의 곱셈을 진행할 때, int 범위를 안 벗어나도록 모듈라 연산을 적절히 하는 것 또한 핵심이였습니다.

#include <iostream>

using namespace std;

 

const int MOD = 1000000007;

 

//행렬의 성질을 이용하여 피보나치 수열을 구함

class Matrix

{

        int arr[2][2];

        //단위 행렬

        Matrix()

        {

                 arr[0][0] = 1;

                 arr[0][1] = 0;

                 arr[1][0] = 0;

                 arr[1][1] = 1;

        }

        Matrix(int a, int b, int c, int d)

        {

                 arr[0][0] = a;

                 arr[0][1] = b;

                 arr[1][0] = c;

                 arr[1][1] = d;

        }

 

        Matrix operator*(Matrix &m)

        {

                 Matrix result = Matrix(0, 0, 0, 0);

                 for (int i = 0; i < 2; i++)

                         for (int j = 0; j < 2; j++)

                                 for (int k = 0; k < 2; k++)

                                          result.arr[i][j] = (result.arr[i][j] + 1LL * arr[i][k] * m.arr[k][j] % MOD) % MOD;

                 return result;

        }

 

        Matrix fastPow(long long N)

        {

                 if (N == 0)

                         return Matrix();

 

                 Matrix result = (*this).fastPow(N / 2);

                 result = result * result;

                 if (N % 2)

                         result = (*this)*result;

                 return result;

        }

 

        friend int fibonacci(long long N);

};

 

//유클리드 호제법

long long GCD(long long a, long long b)

{

        if (a%b == 0)

                 return b;

        return GCD(b, a % b);

}

 

int fibonacci(long long N)

{

        if (N == 0)

                 return 0;

 

        //블로그 POJ 문제를 보면 이해가 될 코드

        Matrix result(1, 1, 1, 0);

        return result.fastPow(N - 1).arr[0][0];

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        long long N, M;

        cin >> N >> M;

 

        cout << fibonacci(GCD(N, M)) << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~