11778 피보나치 수와 최대공약수 행렬 계산 방법

누가 포스팅 해놓은 것도 없고, 찾으려고하니 왜 이렇게 생각해야 되는게 많은 건지...

일단 메모리 제한이 256MB라 메모이제이션 혹은 DP를 생각했는데 .. 시간초가 런타임 에러 뿜뿜...

재귀함수를 만들던,, 메모이제이션을 하던 DP를 하던 O(n) 시간이 걸려서 이건 안되겠다...생각했다.

그래서 검색해보니 피보나치 수열을 계산하는 방법 중에 

1. 피사노 주기(Pisano Period)

2. 행렬 곱셈

들이 있었는데 , 1번은 우리가 계산해야 되는 값이 1,000,000,000,000,000,000 처럼 길고 답을 1,000,000 와 같은 값의 나머지로

출력할때 유용하게 쓰인다. 10^k로 나눈 피보나치 수의 나머지들을 반복적인 값의 형태를 띈다. 그것을 피사노 주기!

하지만, 피사노 주기도 O(n)이 걸리기 때문에, 

2번 행렬 곱셈을 사용해야 한다. 

Fn+1	Fn
Fn	Fn-1

요렇게 행렬을 만든다.

1	1
1	0

즉, 이렇게 되는데

이것을 계속하여 제곱해주면, 결국 O(logN)의 속도로 피보나치 수를 구할 수 있다. 

N^1 , N^2, N^4, N^8... 이런식으로 곱하게 되는데 짝 수일 경우에 짝 수 값까지 O(n)만큼 계산 하지 않아도

도달할 수 있다, 만일 홀수라면 같은 행렬을 제곱하지 않고 N^1을 곱해준다. 

1	1
1	0

2	1
1	0

5	2
3	0

또, 여기까지 완성 했으나... 중간에 mod 하는 계산 빼먹고 (곱셈을 다곱해주고 나서 모드 처리해줘야 값이 제대로 나옴)

, gcd를 mod 연산으로 하지 않아 시간초과가 걸렸다. 

다른 사람들보다 코드가 길긴 하지만 원리대로 만든 것 같다. 

소스보기

#include <iostream>

#include <vector>

using namespace std;

typedef vector<vector<unsigned long long>> matrix;

unsigned long long mod = 1000000007;

matrix operator * (matrix &a, matrix &b){

    //행렬을 이용한 logN 이걸리는 피보나치 수열 구하기

    long long n=a.size();

    matrix c(2, vector<unsigned long long>(n));

    for(int i=0; i<n; i++){

        for(int j=0; j<n; j++){

            for(int k=0; k<n; k++){

                c[i][j] += a[i][k] * b[k][j];

            }

            c[i][j] %= mod;

        }

    }

    return c;

}

unsigned long long gcd(unsigned long long v,unsigned long long u){

    //유클리드 호제법을 이용해서 gcd 구하기

    unsigned long long mod = u % v;

    while(mod > 0){

        u = v;

        v = mod;

        mod = u % v;

    }

    return v;

}

int main(){

    unsigned long long n=0,m=0;

    unsigned long long rgcd=0;

    cin >> n >> m;

    rgcd = gcd(n,m);

    matrix ans = {{1,0},{0,1}};

    //1을 곱했을때와 같은 역할 하는 행렬

    matrix a = {{1,1},{1,0}};

    // 1 , 1 fb(2),fb(1)

    // 1 , 0 fb(1),fb(0)

    while(rgcd>0){

        if(rgcd%2==1){

            //홀수일 경우에 그냥 한번 곱함

            ans = ans * a;

        }

        a = a * a;

        //짝수일 경우에는 2번 곱함

        rgcd /= 2;

    }

    cout << ans[0][1]%mod << endl;

    return 0;

}