Problem 359
Hilbert’s New Hotel
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、2、3等等）在希尔伯特最新的无穷旅馆前排队想要住一间房。旅馆有无穷层（分别标号为1、2、3等等），每一层有无穷间房间（分别标号为1、2、3等等）。
一开始这个旅馆是空的。希尔伯特宣布了以下分配房间的规则：第n个人将在满足以下两个条件之一的最低楼层中获得编号最小的空房间：
- 这层楼是空的
- 这层楼不是空的，前一个住进这层楼的是第m个人，且m + n为完全平方数
第1个人住进第1层的房间1，因为第1层是空的。
第2个人无法住进第1层的房间2，因为1 + 2 = 3不是完全平方数。
第2个人只得住进第2层的房间1，因为第2层是空的。
第3个人住进第1层的房间2，因为1 + 3 = 4是完全平方数。
最终，队伍中的每个人都住进了旅馆中的一个房间。
若第f层的房间r住着第n个人，则记P(f, r)为n，若没有住人则记为0。以下是其中一些例子：
P(1, 1) = 1
P(1, 2) = 3
P(2, 1) = 2
P(10, 20) = 440
P(25, 75) = 4863
P(99, 100) = 19454
对于所有满足f × r = 71328803586048的正数f和r，求P(f, r)的和，并给出其最后8位数字作为你的答案。