POJ 1320 Street Numbers Pell方程

http://poj.org/problem?id=1320

题意很简单,有序列 1,2,3...(a-1),a,(a+1)...b 要使以a为分界的前缀和和后缀和相等求a,b

因为序列很特殊所以我们用数学方法就可以解决 :

求和: a*(a-1)/2 = (a+1+b)(b-a)/2

化简: 2a² = b²+ b

两边乘4,构造完全平方项 (2b+1)² - 8a² = 1

令 x = 2*b+1;

y = a;

我们就得到了一个形如Pell方程x²- Dy²= 1 的式子 x²- 8y²= 1

这题就是求Pell方程的第K个解 , 因为方程已经告诉你了

所以我们可以目测出最小解以用来构造矩阵来求出后面的解

下面就是构造系数矩阵的方法:

已知Pell方程为 x²- Dy²= 1

为了得到第k个解,我们需要构造系数矩阵

为了得到系数矩阵,我们必须知道该方程的最小特解 x0,y0

于是我们就能得到系数矩阵:

x_k y_k就是Pell方程的第k个解

对于Pell方程最小特解的求法,可以参照我上一篇 http://www.cnblogs.com/Felix-F/p/3222741.html

当然这题一眼就能看出最小特解为x=3,y=1

用矩阵快速幂小加了一下速 (应该是逗比了..这样反而复杂度高了....直接记录各层次的矩阵就行...

struct matrix

{

    LL ma[][];

};

int n = ;

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;

}

matrix m_pow(matrix a,int n)

{

    if(n == ) return a;

    matrix temp = m_pow(a,n/);

    if(n & ) return temp * temp * a;

    else return temp * temp ;

}

int main()

{

    matrix a;

    a.ma[][] = ;

    a.ma[][] = ;

    a.ma[][] = ;

    a.ma[][] = ;

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

    {

        matrix tmp = m_pow(a,i);

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

        LL b = (s1-)/;

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

        LL a = s2;

        printf("%10.lld%10.lld\n",a,b);

    }

    return ;

}

巴特西

POJ 1320 Street Numbers Pell方程

最新文章

热门文章