Всем привет. Недавно мне в голову пришла следующая задача:↵
Рассмотрим множество точек **_(x, y)_** с целыми координатами таких, что 0 <= x < a и 0 <= y < b. Требуется найти количество остроугольных треугольников с вершинами в этих точках.↵
↵
### Попытки проинтерполировать↵
Ясно, что можно написать функцию **_f(a, b)_**, которая будет искать ответ и работать при этом за `(ab) ^ 3`. Я предположил, что она ведет себя как многочлен от двух переменных степени не более 6. Я попытался её проинтерполировать, используя [эту теорему](https://ru.wikipedia.org/wiki/Комбинаторная_теорема_о_нулях). Но у меня ничего не получилось, так как при мономах степени больше 6 интерполяция давала ненулевой коэффициент.↵
Не получилось также с тупоугольными и прямоугольными треугольниками.↵
↵
<spoiler summary="code (для прямоугольных треугольников)">↵
~~~~~↵
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)↵
- может, кто-нибудь знает задачи, где формула для ответа не очевидна и её можно подобрать этим методом?↵
↵
**UPD:** found formula for the number of right triangles with b = 2: `f(a, 2) = 2 * a * a - 4`, a > 1.
Рассмотрим множество точек **_(x, y)_** с целыми координатами таких, что 0 <= x < a и 0 <= y < b. Требуется найти количество остроугольных треугольников с вершинами в этих точках.↵
↵
### Попытки проинтерполировать↵
Ясно, что можно написать функцию **_f(a, b)_**, которая будет искать ответ и работать при этом за `(ab) ^ 3`. Я предположил, что она ведет себя как многочлен от двух переменных степени не более 6. Я попытался её проинтерполировать, используя [эту теорему](https://ru.wikipedia.org/wiki/Комбинаторная_теорема_о_нулях). Но у меня ничего не получилось, так как при мономах степени больше 6 интерполяция давала ненулевой коэффициент.↵
Не получилось также с тупоугольными и прямоугольными треугольниками.↵
↵
<spoiler summary="code (для прямоугольных треугольников)">↵
~~~~~↵
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)↵
- может, кто-нибудь знает задачи, где формула для ответа не очевидна и её можно подобрать этим методом?↵
↵
**UPD:** found formula for the number of right triangles with b = 2: `f(a, 2) = 2 * a * a - 4`, a > 1.
