Submission

Score: 100

User: wasupum

Problemset: อนุกรม

Language: c

Time: 0.001 second

Submitted On: 2025-10-04 13:17:59

#include <stdio.h>

typedef long long ll;

void mul(ll F[2][2],ll M[2][2]){
    ll a = F[0][0]*M[0][0] + F[0][1]*M[1][0];
    ll b = F[0][0]*M[0][1] + F[0][1]*M[1][1];
    ll c = F[1][0]*M[0][0] + F[1][1]*M[1][0];
    ll d = F[1][0]*M[0][1] + F[1][1]*M[1][1];
    
    F[0][0] = a;
    F[0][1] = b;
    F[1][0] = c;
    F[1][1] = d;
}

void power(ll F[2][2],int n){
    if(n == 0 || n == 1)return;
    
    ll M[2][2] = {{1,1},{1,0}};
    power(F,n/2);
    mul(F,F);
    
    if(n % 2 == 1)mul(F,M);
}

ll fib( int n){
    if(n == 0 )return 0;
    ll F[2][2] = {{1,1},{1,0}};
    power(F,n-1);
    return F[0][0];
}

int main(void){
    int n;
    scanf("%d",&n);
    printf("%lld",fib(n));
    return 0;
}