Всем привет. Недавно мне в голову пришла следующая задача: Рассмотрим множество точек (x, y) с целыми координатами таких, что 0 <= x < a и 0 <= y < b. Требуется найти количество остроугольных треугольников с вершинами в этих точках.
Попытки проинтерполировать
Ясно, что можно написать функцию f(a, b), которая будет искать ответ и работать при этом за (ab) ^ 3
. Я предположил, что она ведет себя как многочлен от двух переменных степени не более 6. Я попытался её проинтерполировать, используя эту теорему. Но у меня ничего не получилось, так как при мономах степени больше 6 интерполяция давала ненулевой коэффициент. Не получилось также с тупоугольными и прямоугольными треугольниками.
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;
}
Данный код узнаёт коэффициент при мономе 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
.
UPD3: Наконец, я написал решение за O((ab) ^ 2)
.
Codeint fast(int a, int b)
{
int ans = 0;
for (int a1=-a+1;a1<=a-1;a1++)
{
for (int b1=-b+1;b1<=b-1;b1++)
{
if (a1 == 0 && b1 == 0) continue;
for (int a2=-a+1;a2<=a-1;a2++)
{
for (int b2=-b+1;b2<=b-1;b2++)
{
if (a2 == 0 && b2 == 0) continue;
// первое условие - скалярное произведение равно 0
// второе условие - векторное произведение < 0 - чтобы не считать одну пару дважды
if (b1 * b2 + a1 * a2 == 0 && a1 * b2 - b1 * a2 < 0)
{
int cnta = a - max(max(abs(a1), abs(a2)), abs(a1 - a2));
int cntb = b - max(max(abs(b1), abs(b2)), abs(b1 - b2));
if (cnta > 0 && cntb > 0) ans += cnta * cntb;
}
}
}
}
}
return ans;
}
Теперь я могу использовать большие значения a
и b
для интерполяции.
Но всё равно кажется странным, что количество прямоугольных треугольников пропорционально (ab) ^ 2
, а не (ab) ^ 3
. Сейчас попробую понять, почему формула не работает для ai <= b ^ 2
.
UPD4: Код, который находит формулу для f(a, b) при a > b ^ 2
и работает за O(b ^ 6)
:
Спойлерint fast(int a, int b)
{
int ans = 0;
for (int a1=-a+1;a1<=a-1;a1++)
for (int b1=-b+1;b1<=b-1;b1++)
{
if (a1 == 0 && b1 == 0) continue;
for (int a2=-a+1;a2<=a-1;a2++)
for (int b2=-b+1;b2<=b-1;b2++)
{
if (a2 == 0 && b2 == 0) continue;
if (b1 * b2 + a1 * a2 == 0 && a1 * b2 - b1 * a2 < 0)
{
int cnta = a - max(max(abs(a1), abs(a2)), abs(a1 - a2));
int cntb = b - max(max(abs(b1), abs(b2)), abs(b1 - b2));
if (cnta > 0 && cntb > 0) ans += cnta * cntb;
}
}
}
return ans;
}
struct polynom
{
ld x0 = 0, x1 = 0, x2 = 0;
void print()
{
cout << x2 << "x^2 + " << x1 << "x - " << -x0 << endl;
}
ld get(ld x)
{
return x2 * x * x + x1 * x + x0;
}
};
void interpolate(int b)
{
polynom P = {0, 0, 0};
vector<int> A = {b * b + 1, b * b + 2, b * b + 3};
ld res = 0;
for (int a: A)
{
int d = 1;
for (int ai: A) if (a != ai) d *= a - ai;
res += (ld)(fast(a, b) - P.get(a)) / d;
}
P.x2 = res;
res = 0;
A.pop_back();
for (int a: A)
{
int d = 1;
for (int ai: A) if (a != ai) d *= a - ai;
res += (ld)(fast(a, b) - P.get(a)) / d;
}
P.x1 = res;
res = 0;
A.pop_back();
for (int a: A)
{
int d = 1;
for (int ai: A) if (a != ai) d *= a - ai;
res += (ld)(fast(a, b) - P.get(a)) / d;
}
P.x0 = res;
P.print();
}
Пытаясь найти закономерность в коэффициентах многочлена P, я обратился к OEIS, но ничего там не нашел :(