2010辽宁省赛G（佩尔方程）

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

using namespace std;

 

int can[1005] = {0};

int a[10005][605]= {0};

int x[6005], y[6005], t[6005];

int h1,h2;

int bb, ee, xx, yy, c, n;

 

void Pell(int ji,int many,int ma,int kk)

{

    if (ji < kk)

        Pell(ji + 1, a[ma][(ji-1)%a[ma][600]+1], ma, kk);

    else

    {

        h1 = 1;

        h2 = 1;

        x[1] = many;

        y[1] = 1;

        return;

    }

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

        t[i] = x[i];

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

        x[i] = y[i];

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

        y[i] = t[i];

    c = h1;

    h1 = h2;

    h2 = c;

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

        if (i <= h1)

            x[i] += many * y[i];

        else

            x[i] = many * y[i];

    if (h2 > h1)

        h1 = h2;

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

        if (x[i] >= 10)

        {

            x[i+1] += x[i] / 10;

            x[i] %= 10;

        }

    while(x[h1] >= 10)

    {

        x[h1+1] = x[h1] / 10;

        x[h1] %= 10;

        h1++;

    }

    x[0] = h1;

}

 

void solve()

{

    int i, j;

    for (j = 1; j <= 31; j++)

        can[j*j] = true;

    for(i = 1; i <= 1000; i++)

    {

        if(!can[i])

        {

            a[i][600]=1;

            bb = 1;

            ee = (int)sqrt((double)i);

            a[i][0] = ee;

            ee =- ee;

            xx = bb;

            yy = ee;

            xx =- yy;

            yy = i - yy * yy;

            n=0;

            while((xx - yy) * (xx - yy) < i || xx >= 0)

            {

                xx -= yy;

                n++;

            }

            a[i][1] = n;

            c = xx, xx = yy, yy = c;

            while(xx != bb || yy != ee)

            {

                a[i][600]++;

                c = xx;

                xx =- yy;

                yy = i - yy * yy;

                yy = yy / c;

                n = 0;

                while ((xx - yy) * (xx - yy) < i || xx >= 0)

                {

                    xx -= yy;

                    n++;

                }

                a[i][a[i][600]] = n;

                c = xx, xx = yy, yy = c;

            }

        }

    }

}

 

int main()

{

    int k;

    solve();

    while(scanf("%d",&k)!=EOF)///ans^2 = k * n ^ 2 + 1,求ans的最小值(k <= 1000)

    {

        if(!can[k])

        {

            if(a[k][600] % 2)

                Pell(1, a[k][0], k, a[k][600]*2);

            else

                Pell(1, a[k][0], k, a[k][600]);

            for (int j = x[0]; j >= 1; j--)

                printf("%d",x[j]);

            printf(" ");

        }

        else

            printf("no solution ");

    }

    return 0;

}

/*非常裸的佩尔方程模板，输入一个数k,求方程ans^2 = k*n*n+1 中ans的最小整数解(n是大于等于一的整数,无上限)，多积累数论，这个原理仍待了解，//求出p2 - D * q2 = 1的基解(最小正整数解),这个可能溢出,有必要的话,用java, 写成类比较好
bool PQA(LLI D, LLI &p, LLI &q) {//来自于PQA算法的一个特例
    LLI d = sqrt(D);
    if ((d + 1) * (d + 1) == D) return false;
    if (d * d == D)             return false;
    if ((d - 1) * (d - 1) == D) return false;//这里是判断佩尔方程有没有解
    LLI u = 0, v = 1, a = int(sqrt(D)), a0 = a, lastp = 1, lastq = 0;
    p = a, q = 1;
    do {
        u = a * v - u;
        v = (D - u * u) / v;
        a = (a0 + u) / v;
        LLI thisp = p, thisq = q;
        p = a * p + lastp;
        q = a * q + lastq;
        lastp = thisp;
        lastq = thisq;
    } while ((v != 1 && a <= a0));//这里一定要用do~while循环
    p = lastp;
    q = lastq;
    //这样求出后的(p,q)是p2 – D * q2 = (-1)k的解，也就是说p2 – D * q2可能等于1也可能等于-1,如果等于1,(p,q)就是解,如果等于-1还要通过(p2 + D * q2,2 * p * q)来求解，如下
    if (p * p - D * q * q == -1) {
        p = lastp * lastp + D * lastq * lastq;
        q = 2 * lastp * lastq;
    }
    return true;
}
*/