Problem 91: Right Triangles with Integer Coordinates

Counting Strategy

We count triangles by the location of the right angle.

1. Right angle at the origin

If the right angle is at $O$, then

Because all coordinates are nonnegative, this happens if and only if one point lies on the positive $x$-axis and the other lies on the positive $y$-axis. Hence this case contributes

2. Right angle on one of the axes, but not at the origin

Suppose the right angle is at $P=(x,0)$ with $1\le x\le 50$. Since $\overrightarrow{PO}=(-x,0)$ is horizontal, orthogonality forces $\overrightarrow{PQ}$ to be vertical, so $Q=(x,y)$ with $1\le y\le 50$. Therefore this contributes another

By symmetry, the same number of triangles have the right angle at a point $(0,y)$ on the $y$-axis. Thus all axis cases together contribute

3. Right angle at an interior lattice point

Now let the right angle be at an interior point

Write

so that $\gcd(a,b)=1$.

We want all lattice points $Q=(X,Y)$ such that $\angle OPQ=90^\circ$. This is equivalent to

that is,

or

Substituting $x=ga$ and $y=gb$, we get

Since $\gcd(a,b)=1$, divisibility implies that there exists $t\in\mathbb Z$ such that

Therefore every lattice point $Q$ giving a right angle at $P$ is of the form

So the primitive step along the line through $P$ perpendicular to $OP$ is

Positive direction

If $t>0$, then

To stay inside the square $[0,50]^2$, we need

Hence

So the number of valid positive steps is

Negative direction

If $t<0$, write $t=-s$ with $s>0$. Then

The bounds become

so

Thus the number of valid negative steps is

For a fixed interior point $P=(x,y)$, the number of triangles with right angle at $P$ is therefore

Summing over all interior lattice points gives the exact formula

Editorial

The clean way to avoid overcounting is to classify triangles by the position of the right angle. The cases at the origin and on the axes are simple and contribute closed forms immediately, so the only real work is when the right angle sits at an interior lattice point $P=(x,y)$.

For such a point, the segment $PQ$ must lie on the line through $P$ perpendicular to $OP$. Writing $g=\gcd(x,y)$ gives the primitive lattice step on that perpendicular line, namely $(y/g,-x/g)$ up to sign. Every valid choice of $Q$ is obtained by moving along this primitive direction until the square boundary is hit. So the search space is constrained to just two one-dimensional walks from each interior point, and the number of admissible steps in each direction is exactly what the formula counts.

Pseudocode

Initialize the total with the three axis-based contributions $3N^2$.

For each interior lattice point $(x,y)$ with $1 \le x,y \le N$:
    Compute $g=\gcd(x,y)$
    Compute the primitive perpendicular step $(y/g,\;x/g)$

    Count how many forward steps keep the point inside the square
    Count how many backward steps keep the point inside the square

    Add both counts to the running total

Return the running total.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity Analysis

There are $N^2$ interior lattice points. Each point requires one gcd computation and $O(1)$ arithmetic. Therefore:

• Time: $O(N^2 \log N)$
• Space: $O(1)$

For $N=50$, this is trivial to evaluate.

Answer

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>

long long count_right_triangles(int n) {
    long long total = 3LL * n * n;

    for (int x = 1; x <= n; ++x) {
        for (int y = 1; y <= n; ++y) {
            const int g = std::gcd(x, y);
            const int step_x = y / g;
            const int step_y = x / g;

            total += std::min((n - x) / step_x, y / step_y);
            total += std::min(x / step_x, (n - y) / step_y);
        }
    }

    return total;
}

int main() {
    const long long answer = count_right_triangles(50);
    assert(answer == 14234);
    std::cout << answer << '\n';
    return 0;
}

"""
Problem 91: Right Triangles with Integer Coordinates

Count right triangles with vertices O=(0,0), P, Q on the integer grid
[0,N] x [0,N] by counting how many lattice points lie on the line through
each possible right-angle vertex and perpendicular to OP.
"""

from math import gcd


def count_right_triangles(n):
    total = 3 * n * n

    for x in range(1, n + 1):
        for y in range(1, n + 1):
            g = gcd(x, y)
            step_x = y // g
            step_y = x // g

            total += min((n - x) // step_x, y // step_y)
            total += min(x // step_x, (n - y) // step_y)

    return total


def solve():
    return count_right_triangles(50)


if __name__ == "__main__":
    answer = solve()
    assert answer == 14234
    print(answer)