有标号依次为$1, 2, 3\ldots$的无穷多人排队等候在希尔伯特的最新旅馆，每人都需要住一间房。

旅馆有无穷多层，层号依次为$1, 2, 3\ldots$。每一层都有无穷多间房间，房号也依次为$1, 2, 3\ldots$。

初始时旅馆是空的，房间分配的规则如下：

第n个人将在满足以下两个条件之一的最低楼层中获得编号最小的空房间：

（1）这层楼是空的。

（2）这层楼不是空的，上一个住进这层楼的是第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$，否则则记为$P(f, r)=0$。以下是其中一些例子： \begin{align*} P(1, 1) &= 1 \\ P(1, 2) &= 3 \\ P(2, 1) &= 2 \\ P(10, 20) &= 440 \\ P(25, 75) &= 4863 \\ P(99, 100) &= 19454 \end{align*} 求$\sum_{f\cdot r=71328803586048} P(f,r)$的最后8位数字。

本题难度:

解答

根据OEIS A083362中的信息和公式有 $$p(f,r)=\begin{cases} \frac{r(r+1)}{2} & f=1 \\ \lfloor\dfrac{f^2}{2}\rfloor & f>1, r=1 \\ \left(2\cdot\lfloor\frac{f}{2}\rfloor+r-1\right)^2-p(f,r-1) & f,r>1 \end{cases}$$ 展开最后一行可得 $$p(f,r)=\begin{cases} \frac{r(r+1)}{2} & f=1 \\ \frac{r(r-1)}{2}+\lfloor\dfrac{f}{2}\rfloor\cdot\left(\lfloor\dfrac{f}{2}\rfloor+r-\left((r+f)\bmod 2\right)\right) & f>1 \end{cases}$$ 而$71328803586048=2^{27}\times 3^{12}$，枚举所有约数并递推计算即得最终结果$40632119$。

p=lambda f,r: r*(r+1)//2 if f==1 else r*(r-1)//2+f//2*(f//2+r-(r+f)%2)*2
print sum(p((1 << a)*(3**b),(1 << (27-a))*(3**(12-b)))%(10**8) for a in range(28) for b in range(13))%(10**8)