Pagini recente » Cod sursa (job #465302) | Cod sursa (job #465351)
Cod sursa(job #465351)
#include <stdio.h>
using namespace std;
#define MOD 666013
long long m[2][3], c[3][3], fix[2][3];
long long z[3][3], copie_z[3][3];
int baza[1001];
long long K;
int i, j, k, aux;
int p, l, lg;
void afisare (int mat[3][3])
{
for (i=1; i<=2; ++i)
{
for (j=1; j<=2; ++j)
printf ("%d ", mat[i][j]);
printf ("\n");
}
printf ("\n\n\n\n\n");
}
void inmultire (long long t[3][3], long long b[3][3])
{
for (i=1; i<=1; ++i)
for (j=1; j<=2; ++j)
for (k=1; k<=2; ++k)
c[i][k] += (t[i][j] * b[j][k]);
for (i=1; i<=1; ++i)
for (j=1; j<=2; ++j)
{
t[i][j] = c[i][j];
c[i][j] = 0;
}
}
void ridica_z (long long t[3][3], long long b[3][3])
{
for (i=1; i<=2; ++i)
for (j=1; j<=2; ++j)
for (k=1; k<=2; ++k)
c[i][k] += (t[i][j] * b[j][k]);
for (i=1; i<=2; ++i)
for (j=1; j<=2; ++j)
{
t[i][j] = c[i][j];
c[i][j] = 0;
}
//afisare(z);
}
int main ()
{
FILE *f = fopen ("kfib.in","r");
FILE *g = fopen ("kfib.out","w");
fscanf (f,"%lld", &K);
copie_z[1][1] = 0;
copie_z[1][2] = copie_z[2][1] = copie_z[2][2] = 1;
z[1][1] = 1;
z[2][2] = 1;
fix[1][1] = 0;
fix[1][2] = 1;
for (l=1; l<=K; ++l)
{
aux = l - 1;
lg = 0;
while (aux)
{
lg ++;
baza[lg] = aux % 2;
aux /= 2;
}
for (p=lg; p>=1; --p)
{
ridica_z(z, z);
if (baza[p])
{
ridica_z(z, copie_z);
}
//afisare(z);
}
fix[1][1] = 0;
fix[1][2] = 1;
inmultire(fix, z);
//afisare(fix);
z[1][1] = 1;
z[1][2] = 0;
z[2][1] = 0;
z[2][2] = 1;
/*z[1][1] = 0;
z[1][2] = z[2][1] = z[2][2] = 1;
z[1][1] = copie_z[1][1];
z[1][2] = copie_z[1][2];
z[2][1] = copie_z[2][1];
z[2][2] = copie_z[2][2];*/
}
fprintf (g,"%lld",fix[1][2]);
fclose(g);
fclose(f);
return 0;
}