Pagini recente » Borderou de evaluare (job #740018) | Cod sursa (job #2634462)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int MOD = 666013;
int n, ans;
int v[5][5];
void printMatrix(int 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 squareMatrix(int x[5][5], int y[5][5])
{
int 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]) % MOD);
aux[i][j] %= MOD;
}
}
}
memcpy(x, aux, sizeof aux);
}
void powMatrix(int p)
{
int aux[5][5];
aux[0][0] = aux[1][1] = 1;
aux[0][1] = aux[1][0] = 0;
while(p > 0)
{
if(p % 2 == 1)
squareMatrix(aux, v);
squareMatrix(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';
cout << 102334155 % MOD;
return 0;
}