Problem Analysis
I need to count right triangles OPQ where O is the origin and P, Q are distinct lattice points - points with integer coordinates - in the square grid [0, N] x [0, N] with N = 50. A triangle has a right angle when two of its edges meet at exactly 90 degrees. The cleanest perpendicularity test is the dot product: two vectors are orthogonal precisely when their dot product is zero. The brute-force route enumerates every pair of points - an O(N^4) loop over the four coordinates - and checks all three vertices for a right angle. For N = 50 that is a few million pairs, tolerable but wasteful and not generalizable. A far better idea is to classify each triangle by *where* its right angle sits, which collapses the four-dimensional search into a two-dimensional sum.
There are exactly three places the right angle can live: at the origin O, at P, or at Q. The right angle at O is easy: vectors OP and OQ both leave the first-quadrant origin, and two such vectors are perpendicular only when one runs along the x-axis and the other along the y-axis. Counting those axis-aligned combinations gives exactly 3*N^2 triangles. The interesting case is a right angle at a non-origin vertex, say P = (x, y). The edge OP points in direction (x, y); the perpendicular direction is (-y, x). To enumerate the lattice points Q lying on that perpendicular line through P, I reduce (-y, x) to its primitive - shortest integer - form by dividing both components by m = gcd(x, y). Each integer step along that primitive direction lands on a lattice point, and I just count how many such steps stay inside the grid. Computing a gcd at each of the O(N^2) grid points costs O(log N), so the whole algorithm runs in O(N^2 log N) - a dramatic improvement over O(N^4).
Solution Approach
Analytical Counting via Primitive Perpendicular Vectors
The Python and C files implement the same algorithm; the C version is a direct translation for speed. I split the total into two additive pieces.
Right angle at the origin. By the axis argument above, these contribute exactly 3 * N^2 triangles. I encode this directly as triangles_at_origin = 3 * coordinate_limit**2. I checked this constant against the N = 2 example: it accounts for the axis-aligned right triangles among the fourteen shown.
Right angle at P (and by symmetry at Q). I iterate over every candidate vertex P = (x, y) with x from 1 to N and y from 1 to N-1. Keeping x, y >= 1 holds OP off the axes, so the perpendicular case stays genuinely distinct from the origin case. For each P, I compute m = gcd(x, y). The primitive perpendicular step is (-y/m, x/m). Stepping from P along that direction, Q moves by y/m horizontally and x/m vertically per step. The number of steps before leaving the grid is bounded two ways: by horizontal room, giving x * m / y, and by remaining vertical room, giving m * (N - y) / x. Both divisions are exact because m divides both x and y. I take the minimum of the two bounds - whichever boundary I hit first - and add it. Stepping in the opposite perpendicular direction mirrors this count, and the right angle can equally sit at Q rather than P; both effects are captured by the final *= 2.
The C code stores the gcd in a local int m and casts to long long before multiplying, so x * m cannot overflow 32 bits if N grows. The Python code expresses the whole sum as one generator passed to sum, using math.gcd from the standard library. The only structural difference is how each language binds the gcd to a name, discussed below.