53 lines
1.3 KiB
Markdown
53 lines
1.3 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4d61000cf542c50ffe9
|
|||
|
|
title: 'Задача 362: Безквадратні числа'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302023
|
|||
|
|
dashedName: problem-362-squarefree-factors
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Розглянемо число 54.
|
|||
|
|
|
|||
|
|
Число 54 може бути розкладене 7 різними способами на один чи більше факторів, більших ніж 1:
|
|||
|
|
|
|||
|
|
$$54, 2 × 27, 3 × 18, 6 × 9, 3 × 3 × 6, 2 × 3 × 9 \text{ and } 2 × 3 × 3 × 3$$
|
|||
|
|
|
|||
|
|
Якщо нам потрібно, щоб всі фактори були безквадратними, залишаються лише два способи: $3 × 3 × 6$ and $2 × 3 × 3 × 3$.
|
|||
|
|
|
|||
|
|
Давайте викличемо $Fsf(n)$ кількість шляхів $n$, щоб можна було розкласти на один чи більше безквадратних факторів, які більше 1, отже $Fsf(54) = 2$.
|
|||
|
|
|
|||
|
|
Нехай $S(n)$ буде $\сумою Fsf(k)$ for $k = 2$ to $n$.
|
|||
|
|
|
|||
|
|
$S(100) = 193$.
|
|||
|
|
|
|||
|
|
Знайдіть $S(10\\,000\\,000\\,000)$.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`squarefreeFactors()` має повертати `457895958010`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(squarefreeFactors(), 457895958010);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function squarefreeFactors() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
squarefreeFactors();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|