63 lines
2.2 KiB
Markdown
63 lines
2.2 KiB
Markdown
---
|
||
id: 5900f4d31000cf542c50ffe6
|
||
title: '問題 359: ヒルベルトの新しいホテル'
|
||
challengeType: 5
|
||
forumTopicId: 302019
|
||
dashedName: problem-359-hilberts-new-hotel
|
||
---
|
||
|
||
# --description--
|
||
|
||
ヒルベルトの最新の無限ホテルで部屋を取ろうと、人々 (1, 2, 3,... の番号付き) が無限に並んでいます。 ホテルには階 (1, 2, 3,... の番号付き) が無限にあり、各階には部屋 (1, 2, 3,... の番号付き) が無限にあります。
|
||
|
||
当初、ホテルに客はいませんでした。 ヒルベルトは、$n$ 番目の人にどのように部屋を割り当てるかを宣言しました。それによれば、$n$ 番目の人は、以下のいずれかを満たす最下階の最初の空き部屋を取ります。
|
||
|
||
- その階が空いている
|
||
- その階が空いておらず、その階で最後に部屋を取った人が $m$ 番目である場合は $m + n$ が完全平方数になる
|
||
|
||
1 階が空いているので、1 番目の人は 1 階の 1 号室を取ります。
|
||
|
||
1 + 2 = 3 は完全平方数ではないので、2 番目の人は 1 階の 2 号室を取れません。
|
||
|
||
しかし 2 階が空いているので、2 番目の人は代わりに 2 階の 1 号室を取ります。
|
||
|
||
1 + 3 = 4 は完全平方数なので、3 番目の人は 1 階の 2 号室を取ります。
|
||
|
||
最終的には、並んでいたすべての人がホテルの部屋を取れます。
|
||
|
||
$P(f, r)$ の結果を次のように定義します: $n$ 番目の人が $f$ 階の $r$ 号室を取る場合は $n$、誰もその部屋を取らない場合は 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}$$
|
||
|
||
$f × r = 71\\,328\\,803\\,586\\,048$ となるすべての正の数 $f$, $r$ について $P(f, r)$ の総和を求め、下位 8 桁を答えなさい。
|
||
|
||
# --hints--
|
||
|
||
`hilbertsNewHotel()` は `40632119` を返す必要があります。
|
||
|
||
```js
|
||
assert.strictEqual(hilbertsNewHotel(), 40632119);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function hilbertsNewHotel() {
|
||
|
||
return true;
|
||
}
|
||
|
||
hilbertsNewHotel();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|