Pagini recente » Borderou de evaluare (job #1810594) | Cod sursa (job #883939) | Borderou de evaluare (job #1029223) | Borderou de evaluare (job #954386) | Cod sursa (job #2634491)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int64_t MOD = 666013;
int64_t n, ans;
int64_t v[5][5];
void printMatrix(int64_t x[5][5])
{
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < 2; j++)
cout << x[i][j] << ' ';
cout << '\n';
}
cout << '\n';
}
void multiplyMatrix(int64_t x[5][5], int64_t y[5][5])
{
int64_t aux[5][5];
memset(aux, 0, sizeof aux);
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < 2; j++)
{
for(int k = 0; k < 2; k++)
{
aux[i][j] += (x[i][k] * y[k][j]);
aux[i][j] %= MOD;
}
}
}
memcpy(x, aux, sizeof aux);
}
void powMatrix(int64_t p)
{
int64_t aux[5][5];
aux[0][0] = aux[1][1] = 1;
aux[0][1] = aux[1][0] = 0;
while(p > 0)
{
if(p % 2 == 1)
multiplyMatrix(aux, v);
multiplyMatrix(v, v);
p /= 2;
}
memcpy(v, aux, sizeof aux);
}
int main()
{
v[0][0] = 0;
v[0][1] = 1;
v[1][0] = 1;
v[1][1] = 1;
in >> n;
powMatrix(n - 1);
ans = v[0][0] + v[1][0];
out << ans % MOD << '\n';
return 0;
}