Detailed mathematical approach

Problem Summary

For each quadruple \((a,b,c,d)\) with \(1\le a,b,c,d\le m\), consider the lattice quadrilateral with vertices \((a,0)\), \((0,b)\), \((-c,0)\), and \((0,-d)\). The task is to count how many such quadrilaterals contain a perfect-square number of interior lattice points.

The implementations do not inspect lattice points one by one inside each polygon. Instead, they convert the geometry into a closed arithmetic formula for the interior count and then test that value against a precomputed set of squares.

Mathematical Approach

Let \(I(a,b,c,d)\) denote the number of interior lattice points of the quadrilateral determined by \((a,b,c,d)\). The whole problem is therefore to count the quadruples for which \(I(a,b,c,d)\) is a square.

Step 1: Write the Quadrilateral in Cyclic Order

The vertices are visited as

$ (a,0)\to(0,b)\to(-c,0)\to(0,-d)\to(a,0). $

Because each vertex lies on one of the coordinate axes, the figure naturally breaks into four right triangles around the origin. That symmetry is what makes the area and boundary formulas compact.

Step 2: Compute the Area

The four triangles have areas \(\frac{ab}{2}\), \(\frac{bc}{2}\), \(\frac{cd}{2}\), and \(\frac{da}{2}\). Adding them gives

$A=\frac{ab+bc+cd+da}{2}.$

Factoring the same expression yields an equivalent form that is convenient in code:

$2A=ab+bc+cd+da=(a+c)(b+d).$

So the area depends only on simple products of neighboring or opposite side lengths on the axes.

Step 3: Count the Boundary Lattice Points

An edge joining \((u,0)\) and \((0,v)\) has displacement \((-u,v)\). A standard lattice-point fact says that such a segment contributes \(\gcd(u,v)\) boundary steps, or equivalently \(\gcd(u,v)+1\) lattice points including both endpoints.

Applying this to the four edges gives the total number of boundary lattice points

$B=\gcd(a,b)+\gcd(b,c)+\gcd(c,d)+\gcd(d,a).$

This is the correct polygon-level boundary count: shared vertices are handled automatically by the formula \(B=\sum \gcd(|\Delta x|,|\Delta y|)\).

Step 4: Apply Pick's Theorem

Pick's theorem states

$A=I+\frac{B}{2}-1.$

Solving for the interior count gives

$I=A-\frac{B}{2}+1=\frac{ab+bc+cd+da-B}{2}+1.$

Substituting the boundary expression produces the exact arithmetic test used by the implementations:

$I(a,b,c,d)=\frac{(a+c)(b+d)-\gcd(a,b)-\gcd(b,c)-\gcd(c,d)-\gcd(d,a)}{2}+1.$

So each quadruple is reduced to one integer, and the geometric question becomes a perfect-square test.

Step 5: Worked Example

Take \((a,b,c,d)=(2,2,2,1)\). Then

$2A=(2+2)(2+1)=12,$

and

$B=\gcd(2,2)+\gcd(2,2)+\gcd(2,1)+\gcd(1,2)=2+2+1+1=6.$

Therefore

$I=\frac{12-6}{2}+1=4.$

Since \(4=2^2\), this quadruple contributes to the answer. The same formula handles every other quadruple without any geometric case split.

How the Code Works

The C++, Python, and Java implementations all follow the same plan. First they precompute \(\gcd(x,y)\) for every \(1\le x,y\le m\). That turns each boundary contribution into a table lookup instead of a fresh gcd computation inside the innermost loop.

Next they precompute all perfect squares up to a safe upper bound. Since \((a+c)(b+d)\le 4m^2\) and \(B\ge 4\), we have

$I\le \frac{4m^2-4}{2}+1=2m^2-1,$

so marking squares up to \(2m^2+1\) is comfortably sufficient.

Finally the implementations run four nested loops over \(a\), \(b\), \(c\), and \(d\). Inside those loops they reuse boundary values already determined by the outer indices, evaluate the formula for \(I(a,b,c,d)\), and increment the answer exactly when that value is square.

For the sample case \(m=4\), the full enumeration gives \(42\), which matches the known reference value.

Complexity Analysis

Building the gcd table stores \(O(m^2)\) values and needs \(O(m^2\log m)\) arithmetic if each entry is computed with the Euclidean algorithm. Marking all relevant squares is \(O(m)\) time with an \(O(m^2)\)-sized lookup table under the bound above. The dominant cost is the exhaustive scan of all \(m^4\) quadruples, with only \(O(1)\) work per quadruple after precomputation. Therefore the overall complexity is \(O(m^4)\) time and \(O(m^2)\) memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=504
2. Pick's theorem: Wikipedia - Pick's theorem
3. Lattice polygon: Wikipedia - Lattice polygon
4. Greatest common divisor: Wikipedia - Greatest common divisor
5. Shoelace formula: Wikipedia - Shoelace formula