Pagini recente » Borderou de evaluare (job #1127014) | Cod sursa (job #806680)
Cod sursa(job #806680)
#include <cstdio>
#include <cstdlib>
FILE*f;
FILE*g;
int a[2][2],y[2][2];
void inmult_matrici1(int e[2][2], int r[2][2]) //e prima matrice si r a doua, care trebuie inmultite
{
long long c[2][2];
long long 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(int e[2][2], int r[2][2]) //e prima matrice si r a doua, care trebuie inmultite
{
long long c[2][2];
long long 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;
}