Мои попытки ускорить куб доTrying to speed up cube to O(1)
Разница между ru1 и en1, 2,162 символ(ов) изменены
Всем привет. Недавно мне в голову пришла следующая задача:↵
Рассмотрим множество точек **_(x, y)_** с целыми координатами таких, что 0 <= x < a и 0 <= y < b. Требуется найти количество остроугольных треугольников с вершинами в этих точках.↵

### Попытки проинтерполировать↵
Ясно, что можно написать функцию **_f(a, b)_**, которая будет искать ответ и работать при этом за `(ab) ^ 3`. Я предположил, что она ведет себя как многочлен от двух переменных степени не более 6. Я попытался её проинтерполировать, используя [эту теорему
Hello, Codeforces. Recently I invented a problem.↵
Consider a set of points **_(x, y)_** with integer coordinates, 0 <= x < a и 0 <= y < b. We want to know the number of acute triangles with vertices at given points.↵

### Trying to interpolate↵
We can write function **_f(a, b)_** which finds the answer and works in `(ab) ^ 3`. I suggested that it is a polynomial of two variables with degree <= 6. I tried to interpolate it using [this theorem
](https://ruen.wikipedia.org/wiki/Комбинаторная_теорема_о_нулях). Но у меня ничего не получилось, так как при мономах степени больше 6 интерполяция давала ненулевой коэффициент.↵
Не получилось также с тупоугольными и прямоугольными треугольниками.↵

<spoiler summary="code (для прямоугольных треугольников
Combinatorial_Nullstellensatz?wprov=srpw1_1). But my code finds non-zero coefficients with monoms with degrees > 6, so my hypothesis was not confirmed.↵
I also failed with right triangles.↵

<spoiler summary="code (for right triangles
)">↵
~~~~~↵
int stupid(int a, int b)↵
{↵
    int ans = 0;↵
    for (int x1=0;x1<a;x1++)↵
        for (int x2=0;x2<a;x2++)↵
            for (int x3=0;x3<a;x3++)↵
                for (int y1=0;y1<b;y1++)↵
                    for (int y2=0;y2<b;y2++)↵
                        for (int y3=0;y3<b;y3++)↵
                        {↵
                            int a = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);↵
                            int b = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);↵
                            int c = (x3 - x2) * (x3 - x2) + (y3 - y2) * (y3 - y2);↵
                            if ((a + b == c) && min(a, min(b, c))) ans++;↵
                        } ↵
    return ans / 2;↵
}↵
signed main()↵
{↵
    int C1 = 5, C2 = 5;↵
    ld res = 0;↵
    for (int a1=4;a1<=C1+3;a1++)↵
    {↵
     for (int a2=4;a2<=C2+3;a2++)↵
     {↵
     int d = 1;↵
     for (int ai=4;ai<=C1+3;ai++) if (ai != a1) d *= a1 - ai;↵
     for (int ai=4;ai<=C2+3;ai++) if (ai != a2) d *= a2 - ai;↵
     res += (ld)(stupid(a1, a2)) / d;↵
     }↵
    }↵
    cout << setprecision(20) << fixed << res;↵
}↵
~~~~~↵
</spoiler>↵

Данный код узнаёт коэффициент при мономе `a ^ (C1 - 1) * b ^ (C2 - 1)`↵
### Что я хотел бы узнать:↵
- решается ли эта задача быстрее, чем за куб↵
- решается ли эта задача за O(1)↵
- может, кто-нибудь знает задачи, где формула для ответа не очевидна и её можно подобрать этим методом
This code finds a coefficient with `a ^ (C1 - 1) * b ^ (C2 - 1)`↵
### What I would like to know:↵
- can this problem be solved faster than O(stupid(a, b))↵
- can this problem be solved in O(1)↵
- maybe, someone knows problems with difficult to find formulas and this method can help to find them
?

История

 
 
 
 
Правки
 
 
  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 Первая редакция (опубликовано)