Cod sursa(job #2587532)

Utilizator sulzandreiandrei sulzandrei Data 22 martie 2020 21:08:03
Problema Al k-lea termen Fibonacci Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");

#define ull long int
#define mod 666013


struct P{
    public:
        ull a,b,c,d;
        P(){
        };
    P(ull x, ull y, ull z, ull w){
    this->a = x; this->b=y; this->c=z; this->d=w;
    }

    P operator *(const P& right){
            P tmp;
            tmp.a = (this->a*right.a + this->b * right.c)%mod;
            tmp.b = (this->a*right.b + this->b*right.d)%mod;
            tmp.c = (this->c*right.a + this->d*right.c)%mod;
            tmp.d = (this->c*right.b + this->d*right.d)%mod;
            this->a = tmp.a;
            this->b = tmp.b;
            this->c = tmp.c;
            this->d=  tmp.d;
            return *this;
    }

};

ull exp(ull k){
    k--;
    P res(1,0,0,1);
    P base(1,1,1,0);
    while(k){
        if(k&1)
            res = res*base;
        base = base*base;
        k >>=1;
    }
    return res.a;
}

int main()
{
    ull k;
    in>>k;
    if(k>0)
        out<<exp(k);
    else
        out<<0;
    return 0;
}