POJ 1320Street Numbers(佩尔方程定理)

本文主要是介绍POJ 1320Street Numbers(佩尔方程定理)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目： LINK

题意：最终是这个意思1+2+3+.....+a == a + a+1 + a+2 + ..... + b;求满足这个式子的(a, b) b由大到小的前10个。
 利用求和公式可以得到 2*a*a == b*b + b; 令b = (y-1)/2,带入得到y*y - 8*a*a = 1.(化成佩尔方程的形式)
可以利用佩尔方程定理，如果D是一个正整数且不是完全平方数
        x*x - D*y*y = 1 总是有正整数解.
    如果(x1, y1)是使x1最小的解，则每个解课通过取幂得到：
    xk + yk*sqrt(D) = (x1 + y1*sqrt(D)) ^k , k = 1, 2, 3, ....
可以知道得到的式子最小解(1, 3) ，可以不断带入求得前10个解

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define INF 1000000000
//typedef __int64 LL;
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGEint x, y;int a, b;// y*y - 8*a*a = 1;x = 3, y = 1;a = 3, b = 1;for(int i = 1; i <= 10; i++) {int aa = a*x + 8 * b * y;int bb = x*b + a*y;printf("%10d%10d\n", bb, (aa-1)/2);a = aa; b = bb;}return 0;
}

这篇关于POJ 1320Street Numbers(佩尔方程定理)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---