Pagini recente » Cod sursa (job #2022154) | Cod sursa (job #2841689) | Cod sursa (job #2331685) | Cod sursa (job #2625514) | Cod sursa (job #1201749)
#include <fstream>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
const long long mod = 666013;
long long Z[3][3],Sol[3][3],aux[3][3],n,i,j;
int main()
{
cin>>n;
--n;
Z[1][1]=0; Z[1][2]=1; Z[2][1]=1; Z[2][2]=1;
for (i=1;i<=2;++i)
for (j=1;j<=2;++j) Sol[i][j]=Z[i][j];
while(n){
if (n%2){
aux[1][1]=((Sol[1][1]*Z[1][1])%mod+(Sol[1][2]*Z[2][1])%mod)%mod;
aux[1][2]=((Sol[1][1]*Z[1][2])%mod+(Sol[1][2]*Z[2][2])%mod)%mod;
aux[2][1]=((Sol[2][1]*Z[1][1])%mod+(Sol[2][2]*Z[2][1])%mod)%mod;
aux[2][2]=((Sol[2][1]*Z[1][2])%mod+(Sol[2][2]*Z[2][2])%mod)%mod;
for (i=1;i<=2;++i)
for (j=1;j<=2;++j) Sol[i][j]=aux[i][j];
--n;
}
else {
aux[1][1]=((Z[1][1]*Z[1][1])%mod+(Z[1][2]*Z[2][1])%mod)%mod;
aux[1][2]=((Z[1][1]*Z[1][2])%mod+(Z[1][2]*Z[2][2])%mod)%mod;
aux[2][1]=((Z[2][1]*Z[1][1])%mod+(Z[2][2]*Z[2][1])%mod)%mod;
aux[2][2]=((Z[2][1]*Z[1][2])%mod+(Z[2][2]*Z[2][2])%mod)%mod;
for (i=1;i<=2;++i)
for (j=1;j<=2;++j) Z[i][j]=aux[i][j];
n/=2;
}
}
cout<<Sol[2][1];
return 0;
}