Pagini recente » Cod sursa (job #2598791) | Cod sursa (job #143457) | Cod sursa (job #3268258) | Cod sursa (job #2658608) | Cod sursa (job #1112055)
#include <fstream>
#include <cstring>
#define mod 666073
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int K, Z[3][3];
void inmultire(const int A[][3], const int B[][3], int C[][3])
{
int aux[3][3];
memset(aux, 0, sizeof(aux));
for (int i=1; i<=2; ++i)
for (int j=1; j<=2; ++j)
{
long long sum=0;
for (int k=1; k<=2; ++k)
sum+=1LL*A[i][k]*B[k][j];
aux[i][j]=(sum%mod);
}
memcpy(C, aux, sizeof(aux));
}
void log_pow(int Z[][3], int K)
{
int res[3][3];
memset(res, 0, sizeof(res));
res[1][1]=res[2][2]=1;
while (K)
{
if (K%2) inmultire(Z, res, res);
inmultire(Z, Z, Z); K/=2;
}
}
int main()
{
f>>K;
Z[0][0]=0; Z[0][1]=1;
Z[1][0]=1; Z[1][1]=1;
log_pow(Z, K-1);
g<<Z[2][2]<<'\n';
return 0;
}