2022-01-21 01:00:18 +05:30
|
|
|
|
---
|
|
|
|
|
|
id: 5900f4051000cf542c50ff18
|
2022-01-22 20:38:20 +05:30
|
|
|
|
title: '問題 153: ガウス整数を調べ上げる'
|
2022-01-21 01:00:18 +05:30
|
|
|
|
challengeType: 5
|
|
|
|
|
|
forumTopicId: 301784
|
|
|
|
|
|
dashedName: problem-153-investigating-gaussian-integers
|
|
|
|
|
|
---
|
|
|
|
|
|
|
|
|
|
|
|
# --description--
|
|
|
|
|
|
|
|
|
|
|
|
式 $x^2 = -1$ が実数 $x$ に対する解を持たないことは周知のとおりです。
|
|
|
|
|
|
|
|
|
|
|
|
しかし虚数 $i$ を導入すると、この式は 2 つの解を持ちます。$x = i$ と $x = -i$ です。
|
|
|
|
|
|
|
|
|
|
|
|
さらに一歩進めると、式 ${(x - 3)}^2 = -4$ は 2 つの複素数の解を持ちます。$x = 3 + 2i$ と $x = 3 - 2i$ です。これらは互いの共役複素数と呼ばれます。
|
|
|
|
|
|
|
|
|
|
|
|
$a + bi$ の形式で表される数は複素数と呼ばれます。
|
|
|
|
|
|
|
|
|
|
|
|
一般に、$a + bi$ と $a − bi$ は互いに共役複素数です。 ガウス整数とは、$a$ と $b$ の両方が整数である複素数 $a + bi$ です。
|
|
|
|
|
|
|
|
|
|
|
|
普通の整数はガウス整数 ($b = 0$ の場合) でもあります。
|
|
|
|
|
|
|
|
|
|
|
|
$b ≠ 0$ であるガウス整数と区別するために、普通の整数を「有理整数」と呼びます。
|
|
|
|
|
|
|
|
|
|
|
|
有理整数 $n$ をガウス整数で割った結果もガウス整数である場合、有理整数を割った方のガウス整数を約数 (divisor) と呼びます。
|
|
|
|
|
|
|
|
|
|
|
|
例えば、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 は 実部が正である約数を 6 つ持ち、それらは {1, 1 + 2i, 1 − 2i, 2 + i, 2 − i, 5} です。
|
|
|
|
|
|
|
|
|
|
|
|
下表は、最初の 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 (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
|
|
|
|
|
|
```
|
