UVA 138 - Street Numbers

Question

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

Anwser

完整的输出是

6 8
35 49
204 288
1189 1681
6930 9800
40391 57121
235416 332928
1372105 1940449
7997214 11309768
46611179 65918161

这个问题用数学语言描述就是,找到正整数n,m,使得他们满足 1+2+3+...+(n-1) = (n+1) + (n+2) + ... m。 把满足条件的n,m的最小的10对打印出来

上面的等式,利用简单的等差数列求和公式可化简为 2*n*n = m*m +m 。也就是求这个不定方程的整数解。

解法一

我的第一个思路是,让m从1开始递增,然后判断(m*m+m)/2是不是完全平方数。如果是就输出。

但是,第10个m是65918161,于是我做了6000万次循环,其中包含了6000万次sqrt操作啊。毫无疑问会超出时间限制。

于是我就想其它办法。

首先,根据n估计m的范围,根据\(2*n*n = m*m +m\)推出必然有\(n < m < \sqrt{2}n\)。但是好像也没太大用途。

然后我偶然发现数字有点规律,就是你看,输出的这两列,近似的是两个等比数列。

于是我就计算了一下比率:

5.833333333
5.828571429
5.828431373
5.828427250
5.828427128
5.828427125
5.828427125
5.828427125
5.828427125

它们会很奇怪的收敛到5.828427125这个数字。而且是向下收敛。

于是这就好办了,跳着往前算。

int main(){
  long i=2;
  for(int count=0;count!=10;){
    long t=i*i+i;
    long t2=sqrt(t/2);
    if(t2*t2*2==t){
      std::cout<<std::setw(10)<<t2<<std::setw(10)<<i<<"\n";
      count++;
      i=5.82842725*i;
    } else i++;
  }
  return 0;
}

蒙对了,但是我不知道为什么是这样。改天仔细想想那个magic number到底怎么来的。这道题其实可以作弊,本地算好之后,把结果直接写死在代码中submit上去。

解法二

后来在网上发现这个问题有简单的递推式,唉,学艺不精,以后不枉称是数学专业毕业的了。

  for(int count=0,a=3,b=2;count!=10;count++){
    std::cout<<b/2<<" "<<(a-1)/2<<"\n";
    int a1=a;
    a=3*a+4*b;
    b=3*b+2*a1;
  }

此博客中的热门博文

少写代码,多读别人写的代码

在windows下使用llvm+clang

tensorflow distributed runtime初窥