Мои попытки ускорить куб до O(1)

Правка ru4, от polosatic, 2023-02-04 18:38:00

Всем привет. Недавно мне в голову пришла следующая задача: Рассмотрим множество точек (x, y) с целыми координатами таких, что 0 <= x < a и 0 <= y < b. Требуется найти количество остроугольных треугольников с вершинами в этих точках.

Попытки проинтерполировать

Ясно, что можно написать функцию f(a, b), которая будет искать ответ и работать при этом за (ab) ^ 3. Я предположил, что она ведет себя как многочлен от двух переменных степени не более 6. Я попытался её проинтерполировать, используя эту теорему. Но у меня ничего не получилось, так как при мономах степени больше 6 интерполяция давала ненулевой коэффициент. Не получилось также с тупоугольными и прямоугольными треугольниками.

code (для прямоугольных треугольников)

Данный код узнаёт коэффициент при мономе a ^ (C1 - 1) * b ^ (C2 - 1)

Что я хотел бы узнать:

  • решается ли эта задача быстрее, чем за куб
  • решается ли эта задача за O(1)
  • может, кто-нибудь знает задачи, где формула для ответа не очевидна и её можно подобрать этим методом?

UPD: найдена формула для количества прямоугольных треугольников с b = 2: f(a, 2) = 2 * a ^ 2 - 4, a > 1.

Теги математика, формула, задача

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en16 Английский polosatic 2023-02-07 09:55:02 82
ru18 Русский polosatic 2023-02-07 09:54:01 93
ru17 Русский polosatic 2023-02-07 05:28:56 129
en15 Английский polosatic 2023-02-07 05:27:56 131
en14 Английский polosatic 2023-02-07 05:25:34 35 Tiny change: 's together, then the' -> 's together and their product remains the same, then the'
ru16 Русский polosatic 2023-02-06 19:10:33 6
en13 Английский polosatic 2023-02-06 19:09:11 4916 Tiny change: ' < b`, let`s swap the' -> ' < b`, let's swap the'
ru15 Русский polosatic 2023-02-06 18:23:23 26 Мелкая правка: 'реугольник. Ясно, чт' -> 'реугольник второго типа. Ясно, чт'
ru14 Русский polosatic 2023-02-06 17:59:05 5245 Мелкая правка: 'видно.\n\n### Нако' -> 'видно.\n\n\n**UPD5:**\n### Нако'
en12 Английский polosatic 2023-02-05 15:32:48 368
ru13 Русский polosatic 2023-02-05 15:32:17 368
ru12 Русский polosatic 2023-02-05 14:43:45 5 Мелкая правка: 'm\n{\n ld x0 = 0, x' -> 'm\n{\n int x0 = 0, x'
en11 Английский polosatic 2023-02-05 14:43:27 5 Tiny change: 'm\n{\n ld x0 = 0, x' -> 'm\n{\n int x0 = 0, x'
en10 Английский polosatic 2023-02-05 14:39:44 22 Tiny change: '* (b - 1)`\n' -> '* (b - 1)`, but it was obvious.\n'
ru11 Русский polosatic 2023-02-05 14:38:59 53 Мелкая правка: 'е нашел :(\n' -> 'е нашел :(, кроме `x2 = b * (b - 1)`, что и так было очевидно.\n'
en9 Английский polosatic 2023-02-05 14:38:03 123 Tiny change: 'nything :(\n' -> 'nything :( except that `x2 = b * (b - 1)`\n'
ru10 Русский polosatic 2023-02-05 14:34:51 107
ru9 Русский polosatic 2023-02-05 14:31:11 1617 Мелкая правка: ' b ^ 2`.\n**UPD4:*' -> ' b ^ 2`.\n\n**UPD4:*'
en8 Английский polosatic 2023-02-05 14:29:36 1612
en7 Английский polosatic 2023-02-05 13:13:18 14 Tiny change: 'stand why interpolation doesn't w' -> 'stand why the formula doesn't w'
ru8 Русский polosatic 2023-02-05 13:12:54 71
en6 Английский polosatic 2023-02-05 13:11:58 81 Tiny change: 'tion doesn`t work wit' -> 'tion doesn't work wit'
en5 Английский polosatic 2023-02-05 13:08:43 2 Tiny change: ' use `ai >= b ^ 2`.\n' -> ' use `ai > b ^ 2`.\n'
ru7 Русский polosatic 2023-02-05 13:08:28 1 Мелкая правка: 'вать `ai >= b ^ 2`.\n' -> 'вать `ai > b ^ 2`.\n'
ru6 Русский polosatic 2023-02-05 12:46:30 1100 Мелкая правка: 'n\nТеперь у могу испо' -> 'n\nТеперь я могу испо'
en4 Английский polosatic 2023-02-05 12:41:12 1081 Tiny change: '}\n }\n return ans' -> '}\n }\n return ans'
ru5 Русский polosatic 2023-02-04 20:45:05 204
en3 Английский polosatic 2023-02-04 20:43:23 188 Tiny change: ', a > 1.\n**UPD:**' -> ', a > 1.\n\n**UPD:**'
ru4 Русский polosatic 2023-02-04 18:38:00 100
en2 Английский polosatic 2023-02-04 18:37:15 106
ru3 Русский polosatic 2023-02-04 18:36:35 4 Мелкая правка: ') = 2 * a * a - 4`, a >' -> ') = 2 * a ^ 2 - 4`, a >'
ru2 Русский polosatic 2023-02-04 18:24:17 107 Мелкая правка: 'for the nuber of rig' -> 'for the number of rig'
en1 Английский polosatic 2023-02-02 16:59:49 2162 Initial revision for English translation
ru1 Русский polosatic 2023-02-02 16:29:41 2268 Первая редакция (опубликовано)