63 lines
2.6 KiB
Markdown
63 lines
2.6 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^{\text{th}}$ отримує номер: $n$ дістане першу вільну кімнату на найнижчому поверсі за таких умов:
|
||
|
||
- поверх пустий
|
||
- поверх не пустий, а особа $m$ останньою отримала там кімнату, тоді $m + n$ ідеальний квадрат
|
||
|
||
Особа 1 отримує кімнату 1 на поверсі 1, оскільки він пустий.
|
||
|
||
Особа 2 не отримує кімнату 2 на поверсі 1, оскільки 1 + 2 = 3 не створює ідеальний квадрат.
|
||
|
||
Натомість особа 2 отримує кімнату 1 на поверсі 2, оскільки він пустий.
|
||
|
||
Особа 3 отримує кімнату 2 на поверсі 1, оскільки 1 + 3 = 4 створює ідеальний квадрат.
|
||
|
||
Згодом, кожна людина з рядку отримує кімнату в готелі.
|
||
|
||
Визначте $P(f, r)$ як $n$, якщо особа $n$ займає кімнату $r$ на поверсі $f$, та 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}$$
|
||
|
||
Знайти суму усіх $P(f, r)$ для всіх додатних $f$ і $r$, такі як $f × r = 71\\, 28\\,803\\,586\\,048$ і вказати останні 8 цифр як відповідь.
|
||
|
||
# --hints--
|
||
|
||
`hilbertsNewHotel()` має повернути `40632119`.
|
||
|
||
```js
|
||
assert.strictEqual(hilbertsNewHotel(), 40632119);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function hilbertsNewHotel() {
|
||
|
||
return true;
|
||
}
|
||
|
||
hilbertsNewHotel();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|