hdu2281&&POJ1320——Pell方程

hdu2281

输入一个 $N$，求最大的 $n$（$n \leq N$）和 $x$，使得 $x^2 = \frac{1^2+2^2+...+n^2}{n}$.

分析：

将右边式子的分子求和化简，有：$x^2 = \frac{(n+1)(2n+1)}{6}$.

变换成：$(4n+3)^2-48x^2 = 1$.

这就是佩尔方程的形式，且样例给出了最小整数解(7, 1)。

求出long long范围内的所有解（也就9个）

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;

vector<ll>nn, xx;

void init()

{

    ll pre_x = , pre_y = ;

    nn.push_back(), xx.push_back();

    for(int i;;i++)

    {

        ll tmpx = pre_x* + pre_y**;

        ll tmpy = pre_x* + pre_y*;

        if(tmpx < )  break;

        if((tmpx-)% == )

        {

            nn.push_back((tmpx-)/);

            xx.push_back(tmpy);

        }

        pre_x = tmpx; pre_y = tmpy;

    }

    nn.push_back((ll)1e18+);  //设置一个边界

}

int main()

{

    init();

    //printf("%d\n", nn.size());

    while(scanf("%lld", &n) ==  && n)

    {

        for(int i = ;i < nn.size();i++)

        {

            if(n < nn[i])

            {

                printf("%lld %lld\n", nn[i-], xx[i-]);

                break;

            }

        }

    }

}

POJ 1320

题意：有 m 个编号从 1 到 m 的房子，问是否存在 1+2+3+...+ (N-1)=(N+1)+(N+2)+...+(M)，求出前 10 个 n、m

分析：

将左右两端的等差数列求和，有：$(2m+1)^2-8n^2=1$

易知佩尔方程 $x^2-8y^2=1$ 的最小解为 (3, 1)，按递推式可求出其他的解。

#include<cstdio>

using namespace std;

int main()

{

    int x = , y = ;

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

    {

        int tmpx = x* + y**;

        int tmpy = x* + y*;

        printf("%10d%10d\n", tmpy, (tmpx-)/);  //易知tmpx一定是奇数，所以不必判断

        x = tmpx, y = tmpy;

    }

    return ;

}

参考链接：

1. https://blog.csdn.net/u011815404/article/details/88723480

2. https://blog.csdn.net/u011815404/article/details/88723187

巴特西

hdu2281&&POJ1320——Pell方程

hdu2281

POJ 1320

最新文章

热门文章