Street Numbers
| Time Limit: 1000MS |
|
Memory Limit: 10000K |
| Total Submissions: 2529 |
|
Accepted: 1406 |
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
题目要求解1+2+3+...+n=(n+1)+....+m.
要使1+2+3+...+n=(n+1)+....+m.那么n(n+1)/2=(m-n)(n+n+1)/2,即(2m+1)^2-8n^2=1.令x=2m+1，y=n，有x^2-8y^2=1.因此就变成解佩尔方程，而x1=3,y1=1.根据迭代公式：
xn=xn-1*x1+d*yn-1*y1
yn=xn-1*y1+yn-1*x1.
就可以求出前十组解。
//372K 0MS
#include<stdio.h>
#include<math.h>
int main()
{
//freopen("out.txt","w",stdout);
int x1=3,y1=1,d=8,x,y,px=3,py=1;
for(int i=1;i<=10;i++)
{
x=x1*px+d*y1*py;
y=y1*px+x1*py;
printf("%10d%10d\n",y,(x-1)/2);
px=x;py=y;
}
return 0;
}
//368K 0MS
#include<stdio.h>
int main()
{
printf(" 6 8\n 35 49\n 204 288\n 1189 1681\n 6930 9800\n 40391 57121\n 235416 332928\n 1372105 1940449\n 7997214 11309768\n 46611179 65918161\n");
}
POJ 1320 Street Numbers 解佩尔方程
原文：http://blog.csdn.net/crescent__moon/article/details/19335365
