54 lines
2.1 KiB
Markdown
54 lines
2.1 KiB
Markdown
---
|
||
id: 5900f4b91000cf542c50ffcc
|
||
title: 'Задача 333: Спеціальні ділення'
|
||
challengeType: 5
|
||
forumTopicId: 301991
|
||
dashedName: problem-333-special-partitions
|
||
---
|
||
|
||
# --description--
|
||
|
||
Усі додатні цілі числа можна поділити способом, коли кожна частинка розподілу виражається як $2^i \times 3^j$, де $i, j ≥ 0$.
|
||
|
||
Давайте розглянемо лише випадки ділення, коли жодна зі складових не може поділити інші складові. До прикладу, поділ $17 = 2 + 6 + 9 = (2^1 \times 3^0 + 2^1 \times 3^1 + 2^0 \times 3^2)$ не був би допустимим, оскільки 6 ділиться на 2. Не допустимий й поділ $17 = 16 + 1 = (2^4 \times 3^0 + 2^0 \times 3^0)$, оскільки 16 ділиться на 1. Єдиним правильним поділом 17 є $8 + 9 = (2^3 \times 3^0 + 2^0 \times 3^2)$.
|
||
|
||
Для багатьох цілих чисел існує декілька варіантів допустимого поділу, починаючи з 11, котре має два шляхи ділення.
|
||
|
||
$$\begin{align} & 11 = 2 + 9 = (2^1 \times 3^0 + 2^0 \times 3^2) \\\\
|
||
& 11 = 8 + 3 = (2^3 \times 3^0 + 2^0 \times 3^1) \end{align}$$
|
||
|
||
Визначимо $P(n)$ як сукупність правильних поділів $n$. Наприклад, $P(11) = 2$.
|
||
|
||
Розглянемо лише прості числа $q$, для яких буде можливим лише один допустимий поділ, як-от $P(17)$.
|
||
|
||
Сума простих чисел $q <100$, таких як $P(q) = 1$ дорівнює 233.
|
||
|
||
Знайдіть суму простих чисел $q < 1\\,000\\,000$ якщо $P(q) = 1$.
|
||
|
||
# --hints--
|
||
|
||
`specialPartitions()` повинен вивести `3053105`.
|
||
|
||
```js
|
||
assert.strictEqual(specialPartitions(), 3053105);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function specialPartitions() {
|
||
|
||
return true;
|
||
}
|
||
|
||
specialPartitions();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|