Задача 450
Гипоциклоида и точки сетки

Гипоциклоида - это кривая, очерчиваемая точкой на маленькой окружности, катящейся внутри большей окружности. Параметрические уравнения гипоциклоиды с центром в начале координат, начиная с дальней правой точки, даны как:

$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}^{\lfloor \frac {R - 1} 2 \rfloor} S(R, r)$ будет суммой $S(R, r)$ для натуральных R и r, $R\leq N$ и $2r < R$.

Известно:
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)}
Замечание: (-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) = 580442; T(103) = 583108600.

Найдите T(106).

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net