题目描述
一位计算机程序员住在一条街上，街上的房屋从111开始依次编号。每天晚上她遛狗时，都会随机选择向左或向右走，沿着街道一直走到尽头再折返。某天晚上，她计算了途中经过的房屋的街号之和（不包括自己家），然后另一次朝相反方向走时再次计算了这个和。令她惊讶的是，这两个和竟然相等。尽管这取决于她家的编号和街道上房屋的总数，她还是认为这是一个理想的属性，并决定今后选择的所有房屋都应满足这个条件。
你需要编写程序找出满足条件的房屋编号与街道最末房屋编号的配对。已知的前两个配对是：
6 8 35 49输入：无输入。
输出：输出101010行，每行包含一对数字，每个数字右对齐在宽度为101010的字段内（格式如上所示）。
题目分析
设：
- xxx：程序员家的房屋编号
- yyy：街道上最后一间房屋的编号
房屋编号从111到yyy依次递增。当她向左走时，经过的房屋编号为111到x−1x-1x−1；向右走时，经过的房屋编号为x+1x+1x+1到yyy。两次走过的房屋编号之和相等，因此：
∑i=1x−1i=∑i=x+1yi \sum_{i=1}^{x-1} i = \sum_{i=x+1}^{y} ii=1∑x−1i=i=x+1∑yi
解题思路
利用等差数列求和公式：
(1+(x−1))×(x−1)2=((x+1)+y)×(y−x)2 \frac{(1 + (x-1)) \times (x-1)}{2} = \frac{((x+1) + y) \times (y - x)}{2}2(1+(x−1))×(x−1)=2((x+1)+y)×(y−x)
两边同时乘以222消去分母：
(1+x−1)×(x−1)=(x+1+y)×(y−x)x×(x−1)=(x+y+1)×(y−x) (1 + x - 1) \times (x - 1) = (x + 1 + y) \times (y - x) \\ x \times (x - 1) = (x + y + 1) \times (y - x)(1+x−1)×(x−1)=(x+1+y)×(y−x)x×(x−1)=(x+y+1)×(y−x)
展开并整理：
x2−x=xy+y+y−x2−xx2−x=xy+2y−x2−x2x2=y2+y2x2=y(y+1) x^2 - x = xy + y + y - x^2 - x \\ x^2 - x = xy + 2y - x^2 - x \\ 2x^2 = y^2 + y \\ 2x^2 = y(y + 1)x2−x=xy+y+y−x2−xx2−x=xy+2y−x2−x2x2=y2+y2x2=y(y+1)
因此，问题转化为：寻找两个相邻的自然数yyy和y+1y+1y+1，使得它们的乘积等于某个平方数的两倍。即：
y(y+1)=2x2 y(y+1) = 2x^2y(y+1)=2x2
我们需要找到满足这个等式的整数对(x,y)(x, y)(x,y)。
算法实现
我们可以直接枚举yyy，检查y(y+1)/2y(y+1) / 2y(y+1)/2是否为平方数。若是，则对应的xxx即为y(y+1)/2\sqrt{y(y+1) / 2}y(y+1)/2。
已知前两个解为(6,8)(6, 8)(6,8)和(35,49)(35, 49)(35,49)，我们从y=8y = 8y=8开始枚举，直到找到101010个满足条件的配对。
代码实现
// Street Number// UVa ID: 138// Verdict: Accepted// Submission Date: 2016-01-19// UVa Run Time: 0.349s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net// 设程序员所在家的号码为 x，街道最末房子号码为 y，则根据等差序列求和公式有：//// (1 + (x - 1)) * (x - 1) / 2 * 2 = (x + 1 + y) * (y - x) / 2 * 2//// 化简得到：//// 2 * x * x = y * y + y = y * (y + 1)//// 问题转化为：求相邻两个自然数，他们的乘积的一半为一个平方数。#include<bits/stdc++.h>usingnamespacestd;intmain(){intpairs=0;longlonginty=8;while(pairs<10){longlongintx=(longlongint)sqrt(y*(y+1)/2);if((2*x*x)==(y*(y+1))){cout<<setw(10)<<x<<setw(10)<<y<<endl;pairs++;}y++;}return0;}
