Nth Fibonacci Number ~ Ankur's Blog

Resource

	///https://www.spoj.com/problems/MAIN74/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define maxn 100005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const ll Mod = 1000000007;

	void multiply(ll F[2][2], ll M[2][2])
	{
	ll x = ((F[0][0] * M[0][0]) % Mod + (F[0][1] * M[1][0]) % Mod ) % Mod;
	ll y = ((F[0][0] * M[0][1]) % Mod + (F[0][1] * M[1][1]) % Mod ) % Mod;
	ll z = ((F[1][0] * M[0][0]) % Mod + (F[1][1] * M[1][0]) % Mod ) % Mod;
	ll w = ((F[1][0] * M[0][1]) % Mod + (F[1][1] * M[1][1]) % Mod ) % Mod;

	F[0][0] = x;
	F[0][1] = y;
	F[1][0] = z;
	F[1][1] = w;
	}

	void power(ll F[2][2], ll n)
	{
	if(n == 0 \|\| n == 1) return;

	ll M[2][2] = {{1, 1}, {1, 0}};
	power(F, n/2);
	multiply(F, F);
	if(n & 1)
	multiply(F, M);
	}

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


	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif //*/

	int t;
	cin >> t;
	while(t--){
	ll n;
	cin >> n;
	if(n == 0) cout << "0" << endl;
	else if(n == 1) cout << 2 << endl;
	else cout << (fib(n+3)) % Mod<<endl;
	}

	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);

	return 0;
	}

view raw NthFib.cpp hosted with ❤ by GitHub

Ankur's Blog