POJ - 1320:Street Numbers【佩尔方程】

桃扇骨 2023-07-03 08:07 18阅读 0赞

**Driscription**  
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, each printed right justified in a field  
of width 10 (as shown above).

**题意**  
一个计算机程序员住在一个门牌号(从1开始计)连续的街道上，每天晚上她都在这个街道上从头走到尾，有一天晚上她把她走过的门牌号相加起来，下一次她走另一条路还是相加门牌号，令她吃惊的是(我都不知道这有什么好吃惊的)，两个和是相等的。让打出表house number,last number

**思路**  
根据题意列出来公式：  
 1 + 2 + . . . + x = x + ( x + 1 ) + ( x + 2 ) . . . + y 1+2+...+x = x+(x+1)+(x+2)...+y 1\+2\+...\+x=x\+(x\+1)\+(x\+2)...\+y

根据等差数列求和公式计算得：  
 x ∗ ( x + 1 ) / 2 = ( x + y ) ( y − x + 1 ) / 2 x\*(x+1)/2 = (x+y)(y-x+1)/2 x∗(x\+1)/2=(x\+y)(y−x\+1)/2

再进行化简得：  
 ( 2 ∗ y + 1 ) 2 − 8 ∗ x 2 = 1 (2\*y+1)^2-8\*x^2=1 (2∗y\+1)2−8∗x2=1

然后联想到佩尔方程：  
 x 2 + d y 2 = 1 x^2+dy^2=1 x2\+dy2=1

[佩尔方程知识点][Link 1]  
然后根据公式递推10项就可以了。  
注意输出是按照表格右对齐得格式，10位是一个数，前面用空格补齐，就可以用到setw()函数。

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    
    int x,y;
    
    void solve(int d,int &x,int &y) //x^2 - d*(y^2) = 1
    { 
    	y=1;
    	while(1)
    	{ 
    		x=(long long )sqrt(d*y*y+1);
    		if(x*x-d*y*y==1)
    			break;
    		y++;
    	}
    }
    
    int main()
    { 
        int x0=3,y0=1,dx=3,dy=1;
        for(int i=1;i<=10;i++)
        { 
            x=dx*x0+8*y0*dy;
            y=dx*y0+dy*x0;
            cout<<setw(10)<<y<<setw(10)<<(x-1)/2<<endl;
            dx=x;
            dy=y;
        }
        return 0;
    }

[Link 1]: https://blog.csdn.net/weixin_43460224/article/details/104162458