UVa OJ 138 - Street Numbers (门牌号)

Time limit: 3.000 seconds
限时3.000秒

Problem
问题

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.
有一个计算机程序员，她家所在的某条路上的住宅都在路的同一边，编号由1开始依次递增。她每天晚上都要出门溜狗，或向左走或向右走，直到街尾后返回。有一天溜狗时她计算了沿街的门牌号之和（不包括她家的），第二天她走了相反的方向也计算了门牌号之和，结果令她震惊——两次门牌号之和竟然相同。尽管这个结果是由沿街的房子数量以及她家的门牌号决定的，但她仍然觉得这非常奇妙，并决定将此作为以后选择住房的必要条件。

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 and Output
输入与输出

There is no input for this program. 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).
这个程序没有输入。输出前10个能满足上面条件的整数对，每对整数独占一行，每个整数都居右对齐，宽度为10个字符（示例如上）。

Analysis
分析

这道题完全是数论题了。设全部的房子数为n，她住的为k，那么要求的n和k必须满足：

• 1 + 2 + ... + (k-1) = (k+1) + (k+2) + ... + (n)

用等差数列求和公式进行化简：

• (k-1)[1+(k-1)]=(n-k)[(k+1)+n]

再次化简得：

• 2k2=n2+n

题目就转化为求出满足上式的一对正整数：n和k。先将上式两边配方，移项得：

• (2n+1)2-2(2k)2=1

这就成了一个典型的佩尔（Pell）方程，关于该方程的详细内容请参见维基百科：佩尔方程。拉格朗日证明了该方程有解，并用连分式理论求出了其解析解。为了方便程序实现，应将解析解转换为递归解。令：

• x=2n+1，y=2k  (1)

那么有：

• x2-2y2=1  (2)

该方程的最小一组正整数解为(3, 2)，将n=8，k=6代入(1)可得满足题意的最小一组解为(17, 12)。恰好，(17, 12)为(2)式的第二组正整数解。初始计算完毕，迭代公式为：

• xi+1=xix0+nyiy0
• yi+1=xiy0+yix0

在此公式的算法实现中，注意保留前一次的x和y值。若在计算下一个y值前已完成x的迭代，那么y值的迭代将出现错误。

Solution
解答

#include <iomanip>
#include <iostream>
using namespace std;
int main(void) {
        //循环10次，计算出每一组数据，x0和y0为最小解，x和y为迭代解
        for (int i = 0, x0 = 3, y0 = 2, x = x0, y = y0, t; i < 10; ++i, x = t) {
                t = x * x0 + 2 * y * y0; //用t临时保存算得的x
                y = x * y0 + y * x0; //计算出y
                //用x和y解出n和k并输出
                cout << setw(10) << y / 2 << setw(10) << (t - 1) / 2 << endl;
        }
        return 0;
}