Cod sursa(job #587669)
#include <fstream>
#include <cstdlib>
#define MODULO 666013
using namespace std;
typedef unsigned int Mat[2][2];
typedef unsigned long long int uint64;
Mat A, R, X;
inline uint64 gdc( uint64 a, uint64 b )
{
uint64 r=b;
while( b )
{
r=a%b;
a=b;
b=r;
}
return a;
}
inline void Multiply( Mat A, Mat B, Mat& R )
{
R[0][0]=( 1LU*A[0][0]*B[0][0]+1LU*A[0][1]*B[1][0] )%MODULO;
R[0][1]=( 1LU*A[0][0]*B[0][1]+1LU*A[0][1]*B[1][1] )%MODULO;
R[1][0]=( 1LU*A[1][0]*B[0][0]+1LU*A[1][1]*B[1][0] )%MODULO;
R[1][1]=( 1LU*A[1][0]*B[0][1]+1LU*A[1][1]*B[1][1] )%MODULO;
}
inline unsigned int fibonacci( int n )
{
if( 0 == n )
return 0;
if( n <= 2 )
return 1;
n-=1;
A[0][0]=A[0][1]=A[1][0]=R[0][0]=R[1][1]=1;
for( ; n; n>>=1 )
{
if( n&1 )
{
Multiply( R, A, X );
R[0][0]=X[0][0]; R[0][1]=X[0][1];
R[1][0]=X[1][0]; R[1][1]=X[1][1];
--n;
}
Multiply( A, A, X );
A[0][0]=X[0][0]; A[0][1]=X[0][1];
A[1][0]=X[1][0]; A[1][1]=X[1][1];
}
return R[0][0];
}
int main( void )
{
int k;
ifstream in( "kfib.in" );
in>>k;
ofstream out( "kfib.out" );
out<<fibonacci( k )<<'\n';
return EXIT_SUCCESS;
}