HDU 2281 Square Number Pell方程

http://acm.hdu.edu.cn/showproblem.php?pid=2281

又是一道Pell方程

化简构造以后的Pell方程为

求出其前15个解,但这些解不一定满足等式,判断后只有5个满足的情况,直接判断即可

求法可以参照上一篇日志: http://www.cnblogs.com/Felix-F/p/3223323.html

struct matrix

{

    LL ma[][];

};

int n = ;

LL nn[],xx[];

matrix operator * (matrix a,matrix b)

{

    matrix temp;

    memset(temp.ma,,sizeof(temp.ma));

    for(int i = ; i < n ; i++)

        for(int j = ; j < n ; j++)

            for(int k =  ; k < n ; k++)

                temp.ma[i][j] = temp.ma[i][j] + (a.ma[k][i] * b.ma[j][n-k-]);

    return temp;

}

matrix operator + (matrix a,matrix b)

{

    for(int i = ; i < n ; i++)

        for(int j = ; j < n ; j++)

            a.ma[i][j] = (a.ma[i][j] + b.ma[i][j]) ;

    return a;

}

void init()

{

    matrix a;

    a.ma[][] = ;

    a.ma[][] = ;

    a.ma[][] = ;

    a.ma[][] = ;

    matrix temp = a;

    nn[] = ;

    xx[] = ;

    int cnt = ;

    for(int i =  ;i <=  ; i++)

    {

        if(i% == )

        {

            LL s1 = temp.ma[][] *  + temp.ma[][] * ;

            nn[cnt] = (s1 - ) / ;

            LL s2 = temp.ma[][] *  + temp.ma[][] * ;

            xx[cnt++] = s2;

        }

        temp = temp*a;

    }

}

int main()

{

    init();

    LL N;

    while(cin>>N && N)

    {

        for(int i =  ; i >=  ; i--)

        {

            if(N >= nn[i])

            {

                cout<<nn[i]<<" "<<xx[i]<<endl;

                break;

            }

        }

    }

    return ;

}