59 lines
2.2 KiB
Markdown
59 lines
2.2 KiB
Markdown
|
---
|
|||
|
|
id: 5900f53b1000cf542c51004d
|
|||
|
|
title: 'Завдання 462: Перестановка 3-гладких чисел'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302137
|
|||
|
|
dashedName: problem-462-permutation-of-3-smooth-numbers
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
3-гладке число - це ціле число, яке не має простого множника, що більший за 3. Для цілого $N$ ми визначаємо $S(N)$ як набір 3-гладких чисел, менших або рівних $N$. Наприклад, $S(20) = \\{1, 2, 3, 4, 6, 8, 9, 12, 16, 18\\}$.
|
|||
|
|
|
|||
|
|
Ми визначаємо $F(N)$ як кількість перестановок $S(N)$, в яких кожен елемент йде після всіх належних дільників.
|
|||
|
|
|
|||
|
|
Це одна з можливих перестановок для $N = 20$.
|
|||
|
|
|
|||
|
|
- 1, 2, 4, 3, 9, 8, 16, 6, 18, 12.
|
|||
|
|
|
|||
|
|
Дана перестановка не є допустимою, оскільки 12 йде перед своїм дільником - 6.
|
|||
|
|
|
|||
|
|
- 1, 2, 4, 3, 9, 8, 12, 16, 6, 18.
|
|||
|
|
|
|||
|
|
Ми можемо довести, що $F(6) = 5$, $F(8) = 9$, $F(20) = 450$ and $F(1000) ≈ 8.8521816557e\\,21$.
|
|||
|
|
|
|||
|
|
Знайдіть $F({10}^{18})$. Дайте відповідь у вигляді рядка у науковому позначенні, округлену до десяти знаків після коми. Даючи відповідь, використовуйте малі літери `e`, щоб відокремити дріб та показник степеня. Напр. якщо відповідь дорівнює $112\\,233\\,445\\,566\\,778\\,899$, тоді формат відповіді буде `1.1223344557e17`.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`permutationOf3SmoothNumbers()` повинен повернути рядок.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(typeof permutationOf3SmoothNumbers() === 'string');
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
`permutationOf3SmoothNumbers()` повинен повернути рядок `5.5350769703e1512`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(permutationOf3SmoothNumbers(), '5.5350769703e1512');
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function permutationOf3SmoothNumbers() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
permutationOf3SmoothNumbers();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|