[C++] 11444 : 피보나치 수 6

골드 Ⅱ

 

#include <iostream>
#define MOD 1000000007
using namespace std;

long long F[2][2] = { {1,1}, {1,0} };
long long M[2][2] = { {1,1}, {1,0} };

int main() {
    long long N;
    scanf("%lld", &N);
    if (N == 0) {
        printf("0");
        return 0;
    }
    N--;
    while (N) {
        if (N % 2 == 1) {
            long long x1 = (F[0][0] * M[0][0]) % MOD + (F[0][1] * M[1][0]) % MOD;
            long long y1 = (F[0][0] * M[0][1]) % MOD + (F[0][1] * M[1][1]) % MOD;
            long long z1 = (F[1][0] * M[0][0]) % MOD + (F[1][1] * M[1][0]) % MOD;
            long long w1 = (F[1][0] * M[0][1]) % MOD + (F[1][1] * M[1][1]) % MOD;

            F[0][0] = x1 % MOD;
            F[0][1] = y1 % MOD;
            F[1][0] = z1 % MOD;
            F[1][1] = w1 % MOD;
        }
        long long x2 = (M[0][0] * M[0][0]) % MOD + (M[0][1] * M[1][0]) % MOD;
        long long y2 = (M[0][0] * M[0][1]) % MOD + (M[0][1] * M[1][1]) % MOD;
        long long z2 = (M[1][0] * M[0][0]) % MOD + (M[1][1] * M[1][0]) % MOD;
        long long w2 = (M[1][0] * M[0][1]) % MOD + (M[1][1] * M[1][1]) % MOD;
        M[0][0] = x2 % MOD;
        M[0][1] = y2 % MOD;
        M[1][0] = z2 % MOD;
        M[1][1] = w2 % MOD;
        N /= 2;
    }

    printf("%lld", F[1][0]);
    return 0;
}

 

피보나치의 수 정의 점화식을

행렬곱으로 나타내어서 피보나치 수를 log(N)만에 구하는 방법

근데 이것도 FN을 구한답시고 그냥 행렬곱을 N번 곱하고 있으면 똑같이 O(N)이다.

행렬곱으로 하면 log(N)으로 구할 수 있는 이유는

N거듭제곱을 log(N)으로 구할 수 있는 방법이 있기 때문

 

아래 참조

 

x^N 구할 때

O(N) 말고 O(logN)으로 구하는 방법

두 가지 -> 재귀/while문

중 while문 선택했는데 조금 헷갈린다

https://onsil-thegreenhouse.github.io/programming/problem/2018/03/29/problem_math_power/

[Problem] 어떤 수의 n제곱 구하기(백준 1629번) - Onsil's blog