63 lines
2.6 KiB
Markdown
63 lines
2.6 KiB
Markdown
|
---
|
|||
|
|
id: 5900f52e1000cf542c510041
|
|||
|
|
title: 'Задача 450: Гіпоциклоїда та вузли ґратки'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302123
|
|||
|
|
dashedName: problem-450-hypocycloid-and-lattice-points
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Гіпоциклоїда — це крива, яка утворюється точкою малого кола, що котиться по внутрішній стороні іншого кола. Параметричне рівняння гіпоциклоїди з центром на початку координат, яка починається на крайній правій точці, задається так:
|
|||
|
|
|
|||
|
|
$$x(t) = (R - r) \cos(t) + r \cos(\frac{R - r}{r}t)$$
|
|||
|
|
|
|||
|
|
$$y(t) = (R - r) \sin(t) - r \sin(\frac{R - r}{r} t)$$
|
|||
|
|
|
|||
|
|
Де $R$ — радіус великого кола, $r$ — радіус малого кола.
|
|||
|
|
|
|||
|
|
Нехай $C(R, r)$ — це набір окремих точок з координатами, представленими цілими числами, на гіпоциклоїді з радіусом $R$ та $r$, для яких існує відповідне значення $t$, при якому $\sin(t)$ та $\cos(t)$ є раціональними числами.
|
|||
|
|
|
|||
|
|
Нехай $S(R, r) = \sum\_{(x,y) \in C(R, r)} |x| + |y|$ — це сума абсолютних значень точок координат $x$ та $y$ у $C(R, r)$.
|
|||
|
|
|
|||
|
|
Нехай $T(N) = \sum_{R = 3}^N \sum_{r=1}^{\left\lfloor \frac{R - 1}{2} \right\rfloor} S(R, r)$ — це сума натуральних чисел $S(R, r)$ для $R$ і $r$, $R\leq N$ та $2r < R$.
|
|||
|
|
|
|||
|
|
Дано:
|
|||
|
|
|
|||
|
|
$$\begin{align} C(3, 1) = & \\{(3, 0), (-1, 2), (-1,0), (-1,-2)\\} \\\\ C(2500, 1000) = & \\{(2500, 0), (772, 2376), (772, -2376), (516, 1792), (516, -1792), (500, 0), (68, 504), \\\\ &(68, -504),(-1356, 1088), (-1356, -1088), (-1500, 1000), (-1500, -1000)\\} \end{align}$$
|
|||
|
|
|
|||
|
|
**Примітка:** (-625, 0) не елемент $C(2500, 1000)$, оскільки $\sin(t)$ не є раціональним числом для відповідних значень t.
|
|||
|
|
|
|||
|
|
$S(3, 1) = (|3| + |0|) + (|-1| + |2|) + (|-1| + |0|) + (|-1| + |-2|) = 10$
|
|||
|
|
|
|||
|
|
$T(3) = 10$; $T(10) = 524$; $T(100) = 580\\,442$; $T({10}^3) = 583\\,108\\,600$.
|
|||
|
|
|
|||
|
|
Знайдіть $T({10}^6)$.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`hypocycloidAndLatticePoints()` повинен видати `583333163984220900`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(hypocycloidAndLatticePoints(), 583333163984220900);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function hypocycloidAndLatticePoints() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
hypocycloidAndLatticePoints();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|