Solution UVA: 10229 - Modular Fibonacci

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10229 - Modular Fibonacci	Accepted	C++11	0.000	0.000	1342	3 mins ago

Suggest:

- Use template An amazing way to calculate 10^18-th fibonacci number using 25 lines of code. - Codeforces

#include<bits/stdc++.h>

using namespace std;

#define long long long

map<long, long> F;

long M;

long f(long n) {

        if (F.count(n)) return F[n];

        long k=n/2;

        if (n%2==0) { // n=2*k

                return F[n] = (f(k)*f(k) + f(k-1)*f(k-1)) % M;

        } else { // n=2*k+1

                return F[n] = (f(k)*f(k+1) + f(k-1)*f(k)) % M;

        }

}

void reset(){

        F.clear();

        F[0]= F[1]= 1%M;

}

main(){

        ios::sync_with_stdio(false); cin.tie(nullptr);

        long n, m;

        while (cin >> n >> m){

                M = pow(2, m);

                reset();

                cout << (n==0 ? 0 : f(n-1)) << "\n";

        }      

}