fib

#include <iostream>
#include <utility>
#include <tuple>

using namespace std;

pair<uint64_t, uint64_t> fib_intr( const uint64_t n, const uint64_t M){
// returns {fib_n, fib_{n-1}}
    if (n==1)
        return make_pair(1,0);
    else{
        uint64_t Fk, Fkm1;
        tie(Fk, Fkm1) = fib_intr( n/2, M);
        uint64_t F2km1 = (Fk * Fk + Fkm1*Fkm1)%M;
        uint64_t F2k = (Fk*(Fk + 2*Fkm1))%M;
        if (n%2==0) //n==2k
            return make_pair(F2k,F2km1);
        else //n==2k+1
            return make_pair((F2km1 + F2k)%M, F2k);
    }
}

uint64_t fib( const uint64_t n, const uint64_t M){
    if (n==0)
        return 0;
    else
        return fib_intr(n,M).first;
}




int main(int argc, char *argv[]){
    const uint64_t M = 1000000000;
    uint64_t fn=0, fnm1=1;
    for (uint64_t i=0; i<50; i++ ){
        cout<<i<<": "<<fib(i,M)<<" "<<fn<<"\n";
        swap(fn, fnm1);
        fn = (fn+fnm1)%M;
    }
    return 0;
}