55 lines
2.0 KiB
Markdown
55 lines
2.0 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4e51000cf542c50fff6
|
|||
|
|
title: 'Задача 374: Максимальний цілочисельний розділ'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302036
|
|||
|
|
dashedName: problem-374-maximum-integer-partition-product
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Цілочисельний розділ числа $n$ - це спосіб запису $n$ як суми натуральних чисел.
|
|||
|
|
|
|||
|
|
Розділи, які відрізняються лише порядком їх складання, вважаються однаковими. Розділ $n$ на окремі частини - це розділ $n$, у якому кожна частина зустрічається не більше одного разу.
|
|||
|
|
|
|||
|
|
Розподіл 5 на окремі частини:
|
|||
|
|
|
|||
|
|
5, 4 + 1 та 3 + 2.
|
|||
|
|
|
|||
|
|
Нехай $f(n)$ - це максимальний добуток частин будь-якого такого поділу $n$ на окремі частини і нехай $m(n)$ - кількість елементів будь-якого такого поділу $n$ з цим добутком.
|
|||
|
|
|
|||
|
|
Таким чином, $f(5) = 6$ і $m(5) = 2$.
|
|||
|
|
|
|||
|
|
Для $n=10$ розділ з найбільшим добутком становить $10 = 2 + 3 + 5$, що дає $f(10) = 30$ і $m(10) = 3$. І їх добуток, $f(10)\times m(10) = 30\times 3 = 90$
|
|||
|
|
|
|||
|
|
Можна перевірити, що $\sum f(n)\times m(n)$ для $ 1 ≤ n ≤ 100 = 1\\,683\\,550\\,844\\,462 $.
|
|||
|
|
|
|||
|
|
Знайдіть $\sum f(n) \times m(n)$ для $1 ≤ n ≤ {10}^{14}$. Дайте свою відповідь по модулю $982\\,451\\,653$, 50-мільйонне просте число.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`maximumIntegerPartitionProduct()` повинен повернути `334420941`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(maximumIntegerPartitionProduct(), 334420941);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function maximumIntegerPartitionProduct() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
maximumIntegerPartitionProduct();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|