UVa 138 Street Numbers

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