Cod sursa(job #1422669)

Utilizator TeodorescuStefanEduardTeodorescu Stefan Eduard TeodorescuStefanEduard Data 19 aprilie 2015 15:56:45
Problema Submultimi Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<fstream>
 
using namespace std;
 
ifstream f("kfib.in");
ofstream g("kfib.out");
 
long long a[3][3], p[3][3], aux[3][3];
int n , b;
 
void inmulteste()
{
    int i, j, k;
    aux[1][1]=aux[1][2]=aux[2][1]=aux[2][2]=0;
    for (i=1; i<3; ++i)
    {
        for (k=1; k<3; ++k)
            for (j=1; j<3; ++j)
                aux[i][k]=(aux[i][k]+p[i][j]*a[j][k])%b;
    }
 
    for (i=1; i<3; ++i)
        for (j=1; j<3; ++j)
            p[i][j]=aux[i][j];
}
void ridica()
{
    int i, j, k;
 
    aux[1][1]=aux[1][2]=aux[2][1]=aux[2][2]=0;
    for (i=1; i<3; ++i)
    {
        for (k=1; k<3; ++k)
            for (j=1; j<3; ++j)
                aux[i][k]=(aux[i][k]+a[i][j]*a[j][k])%b;
    }
 
    for (i=1; i<3; ++i)
        for (j=1; j<3; ++j) a[i][j]=aux[i][j];
}
 
int main()
{
    f >> n ;
    b = 666013 ;
    n-=2;
    a[1][2]=a[2][1]=a[2][2]=1;
    p[1][1]=p[2][2]=1;
    while(n)
    {
        if(n%2==1)
        {
            inmulteste();
            --n;
        }
        else
        {
            ridica();
            n/=2;
        }
    }
    g<<(p[1][2]+p[2][2])%b;
    return 0;
}