Pagini recente » Borderou de evaluare (job #1621698) | Cod sursa (job #3123518)
#include <fstream>
#define mod 666013
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
void inmultire(long long a[2][2],long long b[2][2],long long c[2][2])
{
for(int i=0; i<=1; i++)
{
for(int j=0; j<=1; j++)
{
c[i][j]=0;
for(int k=0; k<=1; k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j],c[i][j]%=mod;
}
}
}
void copie(long long a[2][2],long long b[2][2])
{
int i,j;
for(i=0;i<=1;i++)
for(j=0;j<=1;j++)
a[i][j]=b[i][j];
}
long long n;
int main()
{
cin>>n;
if(n<=2)
{
return 1;
}
///matricea 1 1
/// 1 0
///trebuie inmultita cu matricea f(n-1)
/// f(n-2)
///de n-2 ori pt a obtine f(n)
/// f(n-1)
n=n-2;
long long a[2][2]= { {1,1},{1,0}};
long long p[2][2]= {{1,0},{0,1}};
long long b[2][2];
while(n!=0)
{
if(n%2==1)
{
inmultire(p,a,b);///b=p*a
copie(p,b);///p=b
}
inmultire(a,a,b);///b=a*a
copie(a,b);///a=b
n=n/2;
}
cout<<(p[0][0]+p[0][1])%mod;
return 0;
}