Hilbert's New Hotel

gracias

这是project euler上最新的一道题.不知大家有没有兴趣.题目是这样的
An infinite number of people (numbered 1, 2, 3, etc.) are lined up to get a room at Hilbert's newest infinite hotel. The hotel contains an infinite number of floors (numbered 1, 2, 3, etc.), and each floor contains an infinite number of rooms (numbered 1, 2, 3, etc.).

Initially the hotel is empty. Hilbert declares a rule on how the nth person is assigned a room: person n gets the first vacant room in the lowest numbered floor satisfying either of the following:

    the floor is empty
    the floor is not empty, and if the latest person taking a room in that floor is person m, then m + n is a perfect square

Person 1 gets room 1 in floor 1 since floor 1 is empty.
Person 2 does not get room 2 in floor 1 since 1 + 2 = 3 is not a perfect square.
Person 2 instead gets room 1 in floor 2 since floor 2 is empty.
Person 3 gets room 2 in floor 1 since 1 + 3 = 4 is a perfect square.

Eventually, every person in the line gets a room in the hotel.

Define P(f, r) to be n if person n occupies room r in floor f, and 0 if no person occupies the room. Here are a few examples:
P(1, 1) = 1
P(1, 2) = 3
P(2, 1) = 2
P(10, 20) = 440
P(25, 75) = 4863
P(99, 100) = 19454

Find the sum of all P(f, r) for all positive f and r such that f × r = 71328803586048 and give the last 8 digits as your answer.

我通过对一些小规模情况的考虑发现有以下规律(纯属猜测,不懂如何证明,因此也不知是否成立)

1  P(1 ,N) = N*(N+1) /2 ;
2  P(N ,1) = N^2 /2( N为偶数)     P(N,1) =(N^2 - 1)/2(N为奇数)
3  P(N ,i+1) 是大于P(N,i)的最小的那个使得P(N,i) + P(N,i+1)为完全平方数的数

即使以上三点成立,以我目前的能力也还是无法解决这个问题,因为计算量还是太大.不知各位是否有兴趣给出更好的解答方法建议.

mathe

写个程序计算出前5000个人的归属，很容易验证满足下面的规律
对于任意给定的a,P(a,b+2)-P(a,b)是公差为2的等差数列。
于是我们只需要再找出每一行的前两个数即可

gracias

谢谢mathe,你的解答已经帮我解过一道题了

mathe

继续分析可以看出
除了前三行前两个数为
1  3
2  7
4  5
以外
对于后面各行，
第k+1行和第k行的差为
[(k+1)/2]*2
而第k行的前两个数的差在k为奇数时是1，k为偶数时是2k+1

gracias

，mathe你好，谢谢你的回复. 但你提到的这个规律我还是没明白如何用于快速求解呀.
利用你提到的规律可以快速求出
p(n ,i+2) - p(n ,i) 但是还是不能确定p(n ,i)呀 !

mathe

也就是每一行的偶数位置的数据可以写成i的二次多项式，同样奇数位置的数据也可以写成i的另外一个二次多项式

mathe

这些性质证明都不难

gracias

完全明白了,谢谢
A3 - A1 = P
A4 - A2 = P + D
A5 - A3 = P + 2D
A6 - A4 = P + 3D ...................
所以:
A3 = A1 +D
A5 = A3 + P +2D = A1 + D +P +2D =  A1 +P + 3D
A7 = A5 + P +3D = A1 +P+ 3D +3D = A1 + P + 6D ........................

gracias

整天忙的人都晕了A3 -A1 ,A4-A2 ,A5 -A3 ......是等差数列,那么 A3 -A1 ，A5-A3 ，A7-A5也是等差数列这都忘了.

gracias

终于完成了