58 lines
1.5 KiB
Markdown
58 lines
1.5 KiB
Markdown
|
---
|
|||
|
|
id: 5900f53d1000cf542c51004f
|
|||
|
|
title: 'Завдання 464: функція Мебіуса та інтервали'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302139
|
|||
|
|
dashedName: problem-464-mbius-function-and-intervals
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Функція Мебіуса, позначена $μ(n)$, визначається наступним чином:
|
|||
|
|
|
|||
|
|
- $μ(n) = (-1)^{ω(n)}$ якщо $n$ є безквадратним (де $ω(n)$ є числом різних простих факторів $n$)
|
|||
|
|
- $μ(n) = 0$ якщо $n$ не є безквадратним.
|
|||
|
|
|
|||
|
|
Нехай $P(a, b)$ буде кількістю цілих чисел $n$ у інтервалі $[a, b]$ як $μ(n) = 1$.
|
|||
|
|
|
|||
|
|
Нехай $N(a, b)$ буде кількістю цілих чисел $n$ у інтервалі $[a, b]$ як $μ(n) = 1$.
|
|||
|
|
|
|||
|
|
До прикладу, $P(2, 10) = 2$ та $N(2, 10) = 4$.
|
|||
|
|
|
|||
|
|
Нехай $C(n)$ буде кількістю пар цілих чисел $(a, b)$ як:
|
|||
|
|
|
|||
|
|
- $1 ≤ a ≤ b ≤ n$,
|
|||
|
|
- $99 \times N(a, b) ≤ 100 \times P(a, b)$, та
|
|||
|
|
- $99 \times P(a, b) ≤ 100 \times N(a, b)$.
|
|||
|
|
|
|||
|
|
До прикладу, $C(10) = 13$, $C(500) = 16\\,676$ та $C(10\\,000) = 20\\,155\\,319$.
|
|||
|
|
|
|||
|
|
Знайдіть $C(20\\,000\\,000)$.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`mobiusFunctionAndIntervals()` повинен повернутися у `198775297232878`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(mobiusFunctionAndIntervals(), 198775297232878);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function mobiusFunctionAndIntervals() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
mobiusFunctionAndIntervals();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|