这题也是一个水题，考英语的。

原题地址：http://poj.org/problem?id=1320

POJ 1320 街道号码

问题描述

一个程序员住在一条街上，这条街的房子被连续地编号（从 1 号开始）。每天晚上她都把狗从家里牵出来遛，并且她会随机的往左或往右转，然后走到街道的尽头再回来。一天晚上，她把街上她走过的房子的号数求了和（除了她自己的）。下一次她走了另外一条路，也把这些房子的号数加起来后，她惊奇地发现，这两个和居然是一样的。虽然这件事（两次的和是一样的）一方面取决于她的房子的号数，另一方面取决于街上房子的数量，但她还是觉得，她的房子（因为有了“让这两次的和是一致的”这种属性）是非常有价值的。并且她决定让以后的房子都表现这样的性质。

写一个程序，求一些满足这个条件的数对。你的程序中一开始的两个数对应该是（数对分别表示她的房子的号码和街上房子的最后一个号码）：

         6         8
        35        49

输入

这个题目木有输入。

输出

输出应该包含 10 行，每行包括 2 个数字，并且按照第二个数（即房子的最大号码）升序排列。两个数都需要 10 的场宽，且右对齐（就像样例输出一样）。

样例输出

         6         8
        35        49

（译注：因为程序没有输入，所以输出只有一种可能性，所以这里的样例输出并没有把所有共 10 行的结果全部输出。而你的程序需要把 10 个结果都输出，并且注意，这 10 个结果包含样例中的两个结果。）

解题思路

其实这种题目用暴力法或者交表都可以。由于有求和公式 [latex]S_{m, n}=\frac{(m+n)(n-m+1)}{2}[/latex], 所以我们只需循环枚举出“最后一个房子”的号码 n, 列出这个等式：[latex]S_{1, x-1}=S_{x+1,n}[/latex], 求整数 x 即可。化简这个式子之后，我惊讶地发现，解居然是：[latex]x=\sqrt{\frac{n(n+1)}{2}}[/latex]. 所以我们只需求出从 1 到最大数的和是完全平方数的就行了。

但是结果是，如果你不交表的话就会超时。所以我还是无耻的交表了，比赛的时候遇到这样的题目，还是要交表。并且注意，生成表的时候，一定要用 64 位的整数，不然过不了。而且题目是有暗示的，既然要 10 个场宽，要区分两个数的话，两个数最大也就 9 位，乘积 18 位，刚好在 64 bit 的整数范围。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Main {
   
    protected static void calculate() {
        int line = 10;
        long x, n;
        for (n = 3; line > 0; ++n) {
            long t = n * (n + 1) / 2;
            x = (long)(Math.sqrt(t) + 0.01);
            if (x * x == t) {
                System.out.printf("%10d%10d\n", x, n);
                --line;
            }
        }
    }
   
    protected static void showTable() {
        System.out.println("         6         8");
        System.out.println("        35        49");
        System.out.println("       204       288");
        System.out.println("      1189      1681");
        System.out.println("      6930      9800");
        System.out.println("     40391     57121");
        System.out.println("    235416    332928");
        System.out.println("   1372105   1940449");
        System.out.println("   7997214  11309768");
        System.out.println("  46611179  65918161");
    }

    public static void main(String[] args) {
        showTable();
    }

}

原创文章，转载请注明来源：http://euyuil.com/2304/poj-1320-street-numbers/