//ciag fibonacciego O(log n)
//Metodą szybkiego potęgowania macierzy
//Jan Wojceichowski
//www.algorytm.org

#include <iostream>

using namespace std;

//Klasa wektora
template<typename T> class Vector {
public:
	Vector(T x = T(0), T y = T(0)) {
		this->x = x;
		this->y = y;
	}

	Vector(const Vector<T> &v) : x(v.x), y(v.y) {
	}

	~Vector() {
	}

	Vector<T> &operator=(const Vector<T> &v) {
		if(this != &v) {
			this->x = v.x;
			this->y = v.y;
		}
		return *this;
	}

	T x, y;
};

//Klasa macierzy o rozmiarze 2x2
template<typename T> class Matrix2x2 {
public:
	Matrix2x2() {
		this->zero();
	}

	Matrix2x2(const Matrix2x2<T> &mx) {
		this->copy(mx.data);
	}

	~Matrix2x2() {
	}

	Matrix2x2<T> &operator=(const Matrix2x2<T> &mx) {
		if(this != &mx) {
			this->copy(mx.data);
		}
		return *this;
	}

	Matrix2x2<T> operator*(const Matrix2x2<T> &mx) {
		Matrix2x2<T> result;
		result.data[0][0] = this->data[0][0] * mx.data[0][0] + this->data[0][1] * mx.data[1][0];
		result.data[0][1] = this->data[0][0] * mx.data[0][1] + this->data[0][1] * mx.data[1][1];
		result.data[1][0] = this->data[1][0] * mx.data[0][0] + this->data[1][1] * mx.data[1][0];
		result.data[1][1] = this->data[1][0] * mx.data[0][1] + this->data[1][1] * mx.data[1][1];
		return result;
	}

	Vector<T> operator*(const Vector<T> &v) {
		Vector<T> result;
		result.x = this->data[0][0] * v.x + this->data[0][1] * v.y;
		result.y = this->data[1][0] * v.x + this->data[1][1] * v.y;
		return result;
	}

	template<typename I> void power(I n) {
		Matrix2x2<T> tmp = (*this);
		this->identity();
		while(n > I(0)) {
			if(n % I(2) == I(0)) {
				tmp = tmp * tmp;
				n /= I(2);
			} else {
				(*this) = (*this) * tmp;
				n -= I(1);
			}
		}
	}

	void zero() {
		this->data[0][0] = T(0);
		this->data[0][1] = T(0);
		this->data[1][0] = T(0);
		this->data[1][1] = T(0);
	}

	void identity() {
		this->data[0][0] = T(1);
		this->data[0][1] = T(0);
		this->data[1][0] = T(0);
		this->data[1][1] = T(1);
	}

	T data[2][2];
private:
	void copy(const T data[2][2]) {
		this->data[0][0] = data[0][0];
		this->data[0][1] = data[0][1];
		this->data[1][0] = data[1][0];
		this->data[1][1] = data[1][1];
	}
};

//Funkcja obliczająca wartosc liczby ciagu Fibonacciego
template<typename T, typename I> T fib(I n) {
	Matrix2x2<T> mx;
	mx.data[0][0] = T(0);
	mx.data[0][1] = T(1);
	mx.data[1][0] = T(1);
	mx.data[1][1] = T(1);
	mx.power(n);
	Vector<T> result = mx * Vector<T>(T(0), T(1));
	return result.x;
}

//Przyklad uzycia
int main(int, char **) {
	typedef unsigned long long Int;

	cout << "Liczby Fibonacciego" << endl;
	cout << "Podaj numer liczby Fibonacciego: ";
	unsigned int n;
	cin >> n;
	cin.ignore();

	Int result = fib<Int>(n);
	cout << n << "-ta liczba Fibonacciego: " << result << endl;

	::getchar();

	return 0;
}