Pagini recente » Cod sursa (job #1060367) | Cod sursa (job #2150129)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define modl 666013
void mcp(int a[4][4], int b[4][4])
{
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
a[i][j] = b[i][j];
}
void prod(int a[4][4], int b[4][4], int c[4][4])
{
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
{
c[i][j] = 0;
for(int k = 0; k < 2; ++k)
c[i][j] = (c[i][j] % modl + (1LL * a[i][k] * b[k][j]) % modl) % modl;
}
}
int a[4][4]
{
{0, 1},
{1, 1}
};
int ret[4][4]
{
{1, 0},
{0, 1}
};
int c[4][4];
int main()
{
int n;
fin >> n;
n--;
for(; n; n >>= 1)
{
if(n & 1)
{
prod(a, ret, c);
mcp(ret, c);
}
prod(a, a, c);
mcp(a, c);
}
fout << ret[1][1];
return 0;
}