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. But my code finds non-zero coefficients with monoms with degrees > 6, so my hypothesis was not confirmed. I also failed with right triangles.**code (for right triangles)**

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?

**UPD:** Found formula for the number of right triangles with b = 2: `f(a, 2) = 2 * a ^ 2 - 4`

, a > 1.

**UPD2:** Many thanks to bronze_coder for finding `O(1)`

solution for constant b: OEIS A189814.

Interpolation should use `ai > b ^ 2`

.

**UPD3:** Finally wrote a `O((ab) ^ 2)`

solution.

**Code**

Now I can interpolate using bigger values of `a`

and `b`

.

But it is quite strange for me that the number of right triangles is directly proportional to `(ab) ^ 2`

instead of `(ab) ^ 3`

. Now I will try to understand why the formula doesn't work with `ai <= b ^ 2`

.

**UPD4:** Code that finds a formula for f(a, b) for `a > b ^ 2`

and works in `O(b ^ 6)`

:

**Spoiler**

I used OEIS to find a regularity between the coefficients of P, but i didn't find anything :( except `x2 = b * (b - 1)`

, but it was obvious.

**UPD5:**

### Finally found a formula and solution in `O(min(a, b) ^ 6)`

If `a < b`

, let's swap them. Now we need to solve it in `O(b ^ 6)`

. If `a <= (b - 1) ^ 2 + 1`

, we can run solution in `O((ab) ^ 3)`

= `O(b ^ 6)`

. Now we need to solve it for `a > (b - 1) ^ 2 + 1`

.

#### Definitions

Consider all right triangles and divide them into 3 types:

triangles without any vertices on the line

`x = a - 1`

triangles with some vertices on the line

`x = a - 1`

and with two sides which are parallel to the x-axis or y-axisother triangles

Let `C(a)`

be the number of third type triangles (some function).

The number of second type triangles is `(a - 1) * b * (b - 1) / 2 * 4`

:

**Proof**

By definition, for every vertex (x, y) of first type triangles, `0 <= x < a - 1`

and `0 <= y < b`

, then the number of the triangles is `f(a - 1, b)`

, by definition of `f`

.

Well, `f(a, b) = f(a - 1, b) + (a - 1) * b * (b - 1) / 2 * 4 + C(a)`

Let's prove that `C(a)`

for every `a > (b - 1) ^ 2 + 1`

has same values.

**Proof**

`C(a)`

is a constant. Let `c`

be this constant.

Well, `f(a, b) = f(a - 1, b) + (a - 1) * b * (b - 1) / 2 * 4 + c`

. After some transforms, we get a formula for `f(a, b)`

using `f((b - 1) ^ 2 + 1, b)`

.

**Transforms**

**Implementation**

Unfortunately, the value of `c`

is different for different values of `b`

and I could not find a regularity between them. Interpolation and OEIS did not help me. There are some things I should do:

- Express
`c`

through`b`

, after all`c`

depends on`b`

only - Solve the problem for
`a <= (b - 1) ^ 2`

faster - Solve the problem for acute triangles.

It will be hard.

**UPD6:** We can speed up the solution to `O(b^5)`

using this idea

Auto comment: topic has been translated by polosatic (original revision, translated revision, compare)The right triangle problem is OEIS A077435

EDIT: OEIS A189814 gives the answer for rectangles.

Thank you! I was quite sure that problem with right triangles can be solved in

`O(a * b)`

But unfortunately,f(n, n)also is not a polynomial of one variable.OMG! I used too small

`ai`

for interpolation with constant b, so it didn't work. After using`ai >= b ^ 2`

everything works!Very nice

A not-implemented solution: let the triangle be tree vectors $$$a,b,c$$$.brute force $$$b-a$$$, and you will get $$$\dfrac{c-a}{|c-a|}$$$(which is rotate it for 90 deg(you can asumme ccw or cw))(In program, you can do it by a ). then you can brute force $$$c-a$$$ by $$$O(a + b)$$$. Then the problem is:

which is trival.

If I understand you correctly, I have already implemented this solution in

UPD3of this blogNo. This solution is $$$O(ab(a+b))$$$.

UPD3 is

`Brute force b-a and c-a, find if b-a ⊥ c-a and find how many triangles with vector b-a and c-a.`

But we can just brute force $$$|c-a|$$$(The length of c-a). the angle of $$$c-a$$$ is found by rotate $$$b-a$$$.

Wow! Good idea! Thank you.

why $$$O(a^2b^2(a+b))$$$ is $$$O(b^5)$$$? may $$$a \gg b^2$$$.

The solution in

UPD5needs to calculate`f((b - 1) ^ 2 + 1, b)`

and`f((b - 1) ^ 2 + 2, b)`

to calculate`f(a, b)`

, it works in`O(b ^ 6)`

, but can be optimized to`O(b ^ 5)`

using your method.Nice resource.