2014
01-10

# UVa-138-Street Numbers(门牌号)数论应用

Time limit: 3.000 seconds

## 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.

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).

## Analysis分析

• 1 + 2 + … + (k – 1) = (k + 1) + (k + 2) + … + (n)    (1)

• (k – 1)[1 + (k – 1)] / 2 = (n – k)[(k + 1) + n] / 2, 两边同乘以2
• (k – 1)[1 + (k – 1)] = (n – k)[(k + 1) + n]    (2)

• 2k2 = n2 + n    (3)

• (2n + 1)2 – 2(2k)2 = 1    (4)

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

• x2 – 2y2 = 1    (6)

• xi+1 = xix0 + nyiy0
• yi+1 = xiy0 + yix0    (7)

• n = (x – 1) / 2, k = y / 2    (8)

## 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;
}

1. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}

2. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.