Cod sursa(job #2450960)

Utilizator TheGodFather2131Alexandru Miclea TheGodFather2131 Data 25 august 2019 11:27:42
Problema Al k-lea termen Fibonacci Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
//ALEXANDRU MICLEA

#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>

using namespace std;

#include <fstream>
ifstream cin("kfib.in"); ofstream cout("kfib.out");

long long n[2][2];
long long ans[2][2];
long long aux[2][2];
int MOD = 666013;

void nans() {
	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j <= 1; j++) {
			for (int k = 0; k <= 1; k++) {
				aux[i][j] += ans[i][k] * n[k][j];
				aux[i][j] %= MOD;
			}
		}
	}
	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j <= 1; j++) {
			ans[i][j] = aux[i][j];
			aux[i][j] = 0;
		}
	}
}

void nsquared() {
	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j <= 1; j++) {
			for (int k = 0; k <= 1; k++) {
				aux[i][j] += n[i][k] * n[k][j];
				aux[i][j] %= MOD;
			}
		}
	}
	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j <= 1; j++) {
			n[i][j] = aux[i][j];
			aux[i][j] = 0;
		}
	}
}

void lgput(int p) {
	while (p) {
		if (p % 2) {
			nans();
		}
		nsquared();
		p /= 2;
	}
}

int main() {

	int p;
	cin >> p;
	
	n[0][0] = 0;
	n[0][1] = 1;
	n[1][0] = 1;
	n[1][1] = 1;

	for (int i = 0; i <= 1; i++) {
		for (int j = 0; j <= 1; j++) {
			ans[i][j] = n[i][j];
		}
	}

	lgput(p);

	cout << ans[0][0];

	return 0;
}