47 lines
2.0 KiB
Markdown
47 lines
2.0 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4bd1000cf542c50ffce
|
|||
|
|
title: 'Задача 335: Збір бобів'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 301993
|
|||
|
|
dashedName: problem-335-gathering-the-beans
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Кожен раз коли Пітеру стає нудно, він розставляє по колу кілька мисок, в кожній з яких знаходиться по одній квасолині. Після цього він дістає всі боби з певної миски та опускає їх по одному в миски, рухаючись за годинниковою стрілкою. Він повторює ці рухи, починаючи з миски, в яку впустив останню квасолинку, поки початкове положення не виникне знову. Наприклад, з 5 мисками він взаємодіє таким чином:
|
|||
|
|
|
|||
|
|
<img class="img-responsive center-block" alt="анімація переміщення бобів в 5 мисках" src="https://cdn.freecodecamp.org/curriculum/project-euler/gathering-the-beans.gif" style="background-color: white; padding: 10px;" />
|
|||
|
|
|
|||
|
|
Таким чином, при 5 чашах Пітеру потрібно 15 ходів, щоб повернутися до вихідної ситуації.
|
|||
|
|
|
|||
|
|
Нехай $M(x)$ є кількістю ходів, необхідних для повернення до вихідної ситуації, починаючи з чаш $x$. Таким чином, $M(5) = 15$. Можна також підтвердити, що $M(100) = 10920$.
|
|||
|
|
|
|||
|
|
Знайдіть $\displaystyle\sum_{k = 0}^{{10}^{18}} M(2^k + 1)$. Дайте відповідь по модулю $7^9$.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`gatheringTheBeans()` має повертати `5032316`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(gatheringTheBeans(), 5032316);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function gatheringTheBeans() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
gatheringTheBeans();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|