Всем привет. Недавно мне в голову пришла следующая задача: Рассмотрим множество точек (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.
