85 lines
4.0 KiB
Markdown
85 lines
4.0 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4051000cf542c50ff18
|
|||
|
|
title: 'Завдання 153. Дослідження Гауссових цілих чисел'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 301784
|
|||
|
|
dashedName: problem-153-investigating-gaussian-integers
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Як ми всі знаємо рівняння $x^2 = -1$ не має реальних розв'язків $x$.
|
|||
|
|
|
|||
|
|
Якщо підставити уявне число $i$, то це рівняння має два рішення: $x = i$ та $x = -i$.
|
|||
|
|
|
|||
|
|
У наступному випадку, рівняння {(x - 3)}^2 = -4$ має два складні рішення: $x = 3 + 2i$ і $x = 3 - 2i$, які називаються складним спряженими числами.
|
|||
|
|
|
|||
|
|
Числа $a + bi$ називаються комплексними числами.
|
|||
|
|
|
|||
|
|
Загалом $a + bi$ та $a - bi$ — спряжені числа. Гауссове ціле число є комплексним числом $a + bi$ таким чином, що і $a$, і $b$ є цілими числами.
|
|||
|
|
|
|||
|
|
Звичайні цілі числа також є простими Гауссовими цілими числами (з $b = 0$).
|
|||
|
|
|
|||
|
|
Щоб відрізняти їх від простих Гауссових чисел з $b ≠ 0$ ми називаємо такі цілі числа "раціональними цілими числами"
|
|||
|
|
|
|||
|
|
Просте Гауссове число називається дільником раціонального цілого числа $n$, якщо результат також є простим Гауссовим числом.
|
|||
|
|
|
|||
|
|
Наприклад, якщо поділити 5 на $1 + 2i$, можемо спростити наступним чином:
|
|||
|
|
|
|||
|
|
Помножте чисельник та знаменник на комплексне спряжене число $1 + 2i$: $1 - 2i$.
|
|||
|
|
|
|||
|
|
Отримаємо:
|
|||
|
|
|
|||
|
|
$$\frac{5}{1 + 2i} = \frac{5}{1 + 2i} \frac{1 - 2i}{1 - 2i} = \frac{5(1 - 2i)}{1 - {(2i)}^2} = \frac{5(1 - 2i)}{1 - (-4)} = \frac{5(1 - 2i)}{5} = 1 - 2i$$
|
|||
|
|
|
|||
|
|
Отже, $1 + 2i$ є дільником 5.
|
|||
|
|
|
|||
|
|
Зверніть увагу, що $1 + i$ не є дільником 5, оскільки:
|
|||
|
|
|
|||
|
|
$$\frac{5}{1 + i} = \frac{5}{2} - \frac{5}{2}i$$
|
|||
|
|
|
|||
|
|
Зверніть увагу, що якщо просте Гауссове ціле число ($a + bi$) є дільником раціонального цілого числа $n$, тоді його спряжене число ($a - bi$) також є дільником $n$. Фактично у числа 5 є шість дільників, такі, що їх формульна сума: {1, 1 + 2i, 1 - 2i, 2 + i, 2 - i, 5}.
|
|||
|
|
|
|||
|
|
Нижче наведена таблиця всіх дільників для перших п'яти додатних раціональних цілих чисел:
|
|||
|
|
|
|||
|
|
| n | Просте Гауссове ціле число з формульною сумою | Сума s(n) цих дільників |
|
|||
|
|
| - | --------------------------------------------- | ----------------------- |
|
|||
|
|
| 1 | 1 | 1 |
|
|||
|
|
| 2 | 1, 1 + i, 1 - i, 2 | 5 |
|
|||
|
|
| 3 | 1, 3 | 4 |
|
|||
|
|
| 4 | 1, 1 + i, 1 - i, 2, 2 + 2i, 2 - 2i, 4 | 13 |
|
|||
|
|
| 5 | 1, 1 + 2i, 1 - 2i, 2 + i, 2 - i, 5 | 12 |
|
|||
|
|
|
|||
|
|
Для дільників з додатною формульною сумою маємо: $\displaystyle\sum_{n=1}^5 s(n) = 35$.
|
|||
|
|
|
|||
|
|
Для $1 ≤ n ≤ {10}^5$, $\displaystyle\sum_{n = 1}^{10}^5} s(n) = 17924657155$.
|
|||
|
|
|
|||
|
|
Що таке $\displaystyle\sum_{n=1}^{{10}^8} s(n)$?
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`sumGaussianIntegers()` має повернути `17971254122360636`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(sumGaussianIntegers(), 17971254122360636);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function sumGaussianIntegers() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
sumGaussianIntegers();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|