Всем привет. Недавно мне в голову пришла следующая задача: Рассмотрим множество точек (x, y) с целыми координатами таких, что 0 <= x < a и 0 <= y < b. Требуется найти количество остроугольных треугольников с вершинами в этих точках.
Попытки проинтерполировать
Ясно, что можно написать функцию f(a, b), которая будет искать ответ и работать при этом за (ab) ^ 3. Я предположил, что она ведет себя как многочлен от двух переменных степени не более 6. Я попытался её проинтерполировать, используя эту теорему. Но у меня ничего не получилось, так как при мономах степени больше 6 интерполяция давала ненулевой коэффициент. Не получилось также с тупоугольными и прямоугольными треугольниками.
Данный код узнаёт коэффициент при мономе a ^ (C1 - 1) * b ^ (C2 - 1)
Что я хотел бы узнать:
- решается ли эта задача быстрее, чем за куб
- решается ли эта задача за O(1)
- может, кто-нибудь знает задачи, где формула для ответа не очевидна и её можно подобрать этим методом?
UPD: найдена формула для количества прямоугольных треугольников с b = 2: f(a, 2) = 2 * a ^ 2 - 4, a > 1.
UPD2: большое спасибо bronze_coder за нахождение решения за O(1) для b = const: OEIS A189814.
Для интерполяции надо использовать ai > b ^ 2. EDIT: ai > (b - 1) ^ 2
UPD3: Наконец, я написал решение за O((ab) ^ 2).
Теперь я могу использовать большие значения a и b для интерполяции.
Но всё равно кажется странным, что количество прямоугольных треугольников пропорционально (ab) ^ 2, а не (ab) ^ 3. Сейчас попробую понять, почему формула не работает для ai <= b ^ 2. EDIT: ai <= (b - 1) ^ 2
UPD4: Код, который находит формулу для f(a, b) при a > b ^ 2 и работает за O(b ^ 6):
Пытаясь найти закономерность в коэффициентах многочлена P, я обратился к OEIS, но ничего там не нашел :(, кроме x2 = b * (b - 1), что и так было очевидно.
UPD5:
Наконец-то нашёл формулу и решение за O(min(a, b) ^ 6)
Если a < b, то поменяем их местами. Теперь нужно решить за O(b ^ 6). Если a <= (b - 1) ^ 2 + 1, то запустим решение за O((ab) ^ 3) = O(b ^ 6). Теперь нужно разобраться с большими a.
Определения
Рассмотрим все прямоугольные треугольники и разделим их на 3 типа:
треугольники, у которых нет вершин на прямой
x = a - 1треугольники, у которых есть вершины на прямой
x = a - 1и две стороны параллельны осям координатостальные треугольники
Обозначим количество треугольников третьего типа за C(a) (какая-то функция от a).
Количество треугольников второго типа можно посчитать по формуле (a - 1) * b * (b - 1) / 2 * 4:
Из определения следует, что для вершин (x, y) треугольников первого типа выполняется 0 <= x < a - 1 и 0 <= y < b, то есть их количество равно f(a - 1, b), по определению функции f.
Итак, f(a, b) = f(a - 1, b) + (a - 1) * b * (b - 1) / 2 * 4 + C(a)
Теперь докажем, что C(a) при всех a > (b - 1) ^ 2 + 1 — константа.
C(a) — константа. Обозначим эту константу за c.
Итак, f(a, b) = f(a - 1, b) + (a - 1) * b * (b - 1) / 2 * 4 + c. Немного преобразований, и мы получаем формулу для f(a, b) через f((b - 1) ^ 2 + 1, b).
К сожалению, c для разных b — разные, и я не смог найти между ними закономерность. Не помогли ни интерполяция, ни OEIS. Осталось несколько вещей, которые надо сделать:
- Выразить
cчерезb, ведьcзависит только отb - Решить задачу для
a <= (b - 1) ^ 2быстрее - Решить задачу для остроугольных треугольников
Будет жёстко.
UPD6: Можно ускорить решение до O(b^5), используя эту идею
