Cod sursa(job #806726)
#include <cstdio>
#include <cstdlib>
FILE*f;
FILE*g;
long long a[2][2],y[2][2];
void inmult_matrici1(long long e[2][2], long long r[2][2]) //e prima matrice si r a doua, care trebuie inmultite
{
long c[2][2];
int i,j,k;
for (i=1;i<=2;i++)
for (j=1;j<=2;j++)
c[i][j]=0;
for (i=1;i<=2;i++)
for (j=1;j<=2;j++)
for (k=1;k<=2;k++)
c[i][j]=(e[i][k]*r[k][j]+c[i][j])%666013;
for (i=1;i<=2;i++)
for (j=1;j<=2;j++)
y[i][j]=c[i][j];
}
void inmult_matrici2(long long e[2][2], long long r[2][2]) //e prima matrice si r a doua, care trebuie inmultite
{
long c[2][2];
int i,j,k;
for (i=1;i<=2;i++)
for (j=1;j<=2;j++)
c[i][j]=0;
for (i=1;i<=2;i++)
for (j=1;j<=2;j++)
for (k=1;k<=2;k++)
c[i][j]=(e[i][k]*r[k][j]+c[i][j])%666013;
for (i=1;i<=2;i++)
for (j=1;j<=2;j++)
a[i][j]=c[i][j];
}
int main()
{
int i;
long k;
f=fopen("kfib.in","r");
g=fopen("kfib.out","w");
fscanf(f,"%d",&k);
if (k==1) fprintf (g,"1");
else
{a[1][1]=0;a[1][2]=1;a[2][1]=1;a[2][2]=1;
y[1][1]=1;y[1][2]=0;y[2][1]=0;y[2][2]=1;
for (i=0;(1<<i)<=(k-1);++i)
{
if (((1<<i)&(k-1))>0)
inmult_matrici1(y,a);
inmult_matrici2(a,a);}
fprintf(g,"%d",y[2][2]);}
return 0;
}