Cod sursa(job #589651)
#include <stdio.h>
#define MOD 1000333
FILE *fin = fopen("kfib.in", "rt");
FILE *fout = fopen("kfib.out", "wt");
long long n, m;
typedef struct mat
{
long long a, b, c;
} mat;
mat getPow(long long int p)
{
mat rez;
if (p <= 1)
{
rez.a = rez.b = 1;
rez.c = 0;
return rez;
}
mat m = getPow(p / 2);
rez.a = m.a * m.a + m.b * m.b;
rez.b = m.a * m.b + m.b * m.c;
rez.c = m.b * m.b + m.c * m.c;
if (p % 2)
{
rez.a += rez.b;
rez.b = rez.a - rez.b;
rez.c = rez.b - rez.c;
}
rez.a %= MOD;
rez.b %= MOD;
rez.c %= MOD;
return rez;
}
long long fib(long long i)
{
if (i == 0) return 0;
mat m = getPow(i);
return m.b;
}
long long gcd(long long n, long long m)
{
if (n % m == 0) return m;
return gcd(m, n % m);
}
int main()
{
fscanf(fin, "%I64d", &n);
fprintf(fout, "%I64d\n", fib(n));
fclose(fin);
fclose(fout);
return 0;
}