Задача 295
Двояковыпуклые прорези

Будем называть выпуклую область, ограниченную двумя окружностями двояковыпуклой прорезью, если:

  • Центры обеих окружностей лежат в узлах координатной сетки.
  • Две окружности пересекаются в двух отличающихся узлах координатной сетки.
  • Внутренняя часть области, ограниченной двумя окружностями, не содержит узлов координатной сетки.

Рассмотрим следующие окружности:
C_(0): x^(2)+y^(2)=25
C_(1): (x+4)^(2)+(y-4)^(2)=1
C_(2): (x-12)^(2)+(y-4)^(2)=65

Окружности C_(0), C_(1) и C_(2) показаны на рисунке ниже.

C_(0) и C_(1) образуют двояковыпуклую прорезь, равно как и C_(0) и C_(2).

Упорядоченную пару положительных действительных чисел (r_(1), r_(2)) будем называть двояковыпуклой парой, если существуют две окружности радиусами r_(1) и r_(2), образующие двояковыпуклую прорезь. Можно убедиться, что (1, 5) и (5, √65) являются двояковыпуклыми парами для рассмотренного выше примера.

Пусть L(N) - число различных двояковыпуклых пар (r_(1), r_(2)), для которых выполняется условие 0 < r _(1) ≤ r_(2) ≤ N.
Можно убедиться, что L(10) = 30 и L(100) = 3442.

Найдите L(100 000).

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