Задача 630
Пересекающиеся прямые

При данном множестве уникальных прямых $L$, пусть $M(L)$ будет количеством прямых в этом множестве, и пусть $S(L)$ будет суммой количеств пересечений с другими прямыми множества для каждой прямой. Например, два множества из трех прямых показаны ниже:

crossed lines

В обоих случаях M(L) равно 3 и S(L) равно 6: каждая из трех прямых пересекается с двумя другими прямыми. Заметим, что даже если прямые пересекаются в одной точке, для каждой прямой это пересечение считается отдельно.

Рассмотрим точки ($T_{2k−1}$, $T_{2k}$) для целого $k >= 1$, сгенерированные следующим образом:

$S_0 = 290797$
$S_{n+1} = {S_n}^2 \:\: \rm{mod} \:\: 50515093$
$T_n = ( S_n \:\: \rm{mod} \:\: 2000 ) − 1000$

Например, первыми тремя точками являются: (527, 144), (−488, 732), (−454, −947). При данных первых $n$ таким образом сгенерированных точках, пусть $L_n$ будет множеством уникальных прямых, образованных соединением каждой точки с каждой другой точкой и продлением полученных отрезков на бесконечное расстояние в обоих направлениях. Можем определить $M(L_n)$ и $S(L_n)$, как описано выше.

Например, $M(L_3) = 3$ и $S(L_3) = 6$. Также, $M(L_{100}) = 4948$ и $S(L_{100}) = 24477690$.

Найдите $S(L_{2500})$.

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