POJ 1320-Street Numbers（解佩尔方程）

淡淡的烟草味﹌ 2022-09-25 00:29 106阅读 0赞

Street Numbers

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;2908</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;1621</td> 
  </tr> 
 </tbody> 
</table>

Description

A computer programmer lives in a street with houses numbered consecutively (from 1) down one side of the street. Every evening she walks her dog by leaving her house and randomly turning left or right and walking to the end of the street and back. One night she adds up the street numbers of the houses she passes (excluding her own). The next time she walks the other way she repeats this and finds, to her astonishment, that the two sums are the same. Although this is determined in part by her house number and in part by the number of houses in the street, she nevertheless feels that this is a desirable property for her house to have and decides that all her subsequent houses should exhibit it.  
Write a program to find pairs of numbers that satisfy this condition. To start your list the first two pairs are: (house number, last number):

6         8
    
            35        49

Input

There is no input for this program.

Output

Output will consist of 10 lines each containing a pair of numbers, in increasing order with the last number, each printed right justified in a field of width 10 (as shown above).

Sample Input

Sample Output

6         8
            35        49

Source

[New Zealand 1990 Division I][],UVA 138

## 题目意思： ##

形如 X^2-d\*Y^2=1 的不定方程被称为佩尔方程。

求解两个不相等的正整数n，m，使得：

1+2+3+…+n=（n+1）+（n+2）+…+m。

## 解题思路： ##

用高斯速算公式分别计算两边式子，合并化简后可以得到：（2\*m +1）^2 - 8\*n^2 =1，即佩尔方程形式。

有迭代公式：

**Xn=Xn-1\*X1+d\*Yn-1\*Y1**

**Yn=Xn-1\*Y1+Yn-1\*X1.**

**……**

**Xn+1=3Xn+8Yn.**

**Yn+1=Xn+3Yn**

**其中X1=3，Y1=1,n和n-1为下标。**

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #define MAXN 1000010
    typedef long long ll;
    using namespace std;
    
    void Search()
    {
        int x,y,x1=3,y1=1,d=8,px=3,py=1;
        for(int i=0; i<10; i++)
        {
            x=x1*px+d*y1*py;
            y=y1*px+x1*py;
            printf("%10d%10d\n",y,(x-1)/2);//输出格式要求右对齐且每个数占10格
            px=x;
            py=y;
        }
    }
    
    int main()
    {
        //ios::sync_with_stdio(false);
        //cin.tie(0);
        Search();
        return 0;
    }
    
    /**
    6         8
    35        49
    **/

[New Zealand 1990 Division I]: http://poj.org/searchproblem?field=source&key=New+Zealand+1990+Division+I