# Cod sursa(job #2753505)

Utilizator Data 23 mai 2021 09:52:29 Al k-lea termen Fibonacci 100 cpp-64 done Arhiva educationala 1.32 kb
``````#include <bits/stdc++.h>
#define NMAX 5
#define int int64_t
#define double long double
#define cin fin
#define cout fout
using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int mod = 666013;
struct matrix {
int values[NMAX][NMAX];
matrix() {
memset(values, 0, sizeof(values));
}
friend matrix operator*(matrix);
void construct(int n)
{
int i;
for(i=0;i<n;i++)
values[i][i]=1;
}
};

matrix operator*(matrix a, matrix b)
{
matrix ans;
for (int i = 0; i < NMAX; i++)
for (int j = 0; j < NMAX; j++)
for (int k = 0; k < NMAX; k++)
ans.values[i][j] = (ans.values[i][j] + (1LL * a.values[i][k] * b.values[k][j])%mod)%mod;
return ans;
}
matrix iNmax;

matrix logPow(matrix x, int n)
{
if (!n) return iNmax;
if (n & 1) return x * logPow(x * x, n >> 1);
return logPow(x * x, n >> 1);
}
int32_t main()
{
iNmax.construct(5);

int t;
cin>>t;
matrix m;
int x,y,z;
int a,b,c;
int zile;
m.values[0][0]=1;
m.values[0][1]=1;
m.values[1][0]=1;
m.values[2][1]=1;

m=logPow(m,t-2);
cout<<(m.values[0][0]* 1+ m.values[0][1]) %mod;

return 0;
}``````