Problem 504: Square on the Inside

Mathematical Analysis

Pick’s Theorem

For a simple polygon with vertices at lattice points:

where $A$ is the area, $i$ is the number of interior lattice points, and $b$ is the number of boundary lattice points.

Area of the Quadrilateral

The quadrilateral has vertices $A(a,0)$, $B(0,b)$, $C(-c,0)$, $D(0,-d)$. Using the Shoelace formula:

Wait — more carefully, the area of this kite-like shape is composed of 4 right triangles:

Boundary Points

The number of lattice points on a line segment from $(x_1, y_1)$ to $(x_2, y_2)$ (excluding one endpoint) is $\gcd(|x_2 - x_1|, |y_2 - y_1|)$.

The four edges contribute:

• $AB$: $\gcd(a, b)$ points (excluding endpoints)
• $BC$: $\gcd(c, b)$ points
• $CD$: $\gcd(c, d)$ points
• $DA$: $\gcd(a, d)$ points

Total boundary points (including 4 vertices):

Wait — each edge from vertex to vertex has $\gcd + 1$ lattice points (including both endpoints). So total boundary points = sum of edge points minus double-counted vertices:

(Each edge contributes $\gcd - 1$ interior points + 2 endpoints. Sum = $\sum(\gcd + 1) - 4$ since each vertex counted twice = $\sum \gcd$.)

Interior Points

From Pick’s Theorem:

We check whether $i$ is a perfect square.

Editorial

We precompute gcd(x, y) for all 1 <= x, y <= 100. We then precompute perfect squares up to max possible i. Finally, iterate over all (a, b, c, d) with 1 <= a, b, c, d <= 100.

Pseudocode

Precompute gcd(x, y) for all 1 <= x, y <= 100
Precompute perfect squares up to max possible i
For all (a, b, c, d) with 1 <= a, b, c, d <= 100:
Return counter
# Optimization

Complexity Analysis

• Time: $O(m^4)$ with precomputed GCD table, which is $100^4 = 10^8$ — feasible.
• Space: $O(m^2)$ for GCD table.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int M = 100;

    // Precompute GCD table
    int g[M + 1][M + 1];
    for (int i = 0; i <= M; i++)
        for (int j = 0; j <= M; j++)
            g[i][j] = __gcd(i, j);

    // Precompute perfect squares
    // Max interior points: ((M+M)*(M+M))/2 + 1 = 2*M*M + 1 = 20001
    int max_i = 2 * M * M + 1;
    vector<bool> is_sq(max_i + 1, false);
    for (int k = 0; (long long)k * k <= max_i; k++)
        is_sq[k * k] = true;

    int count = 0;

    for (int a = 1; a <= M; a++) {
        for (int b = 1; b <= M; b++) {
            for (int c = 1; c <= M; c++) {
                for (int d = 1; d <= M; d++) {
                    int boundary = g[a][b] + g[b][c] + g[c][d] + g[d][a];
                    int twice_area = (a + c) * (b + d);
                    int twice_i = twice_area - boundary + 2;
                    // i must be integer, so twice_i must be even
                    if (twice_i % 2 != 0) continue;
                    int interior = twice_i / 2;
                    if (interior >= 0 && interior <= max_i && is_sq[interior])
                        count++;
                }
            }
        }
    }

    cout << count << endl;
    return 0;
}

from math import gcd, isqrt

def solve():
    M = 100

    # Precompute GCD table
    g = [[0] * (M + 1) for _ in range(M + 1)]
    for i in range(M + 1):
        for j in range(M + 1):
            g[i][j] = gcd(i, j)

    # Precompute perfect squares
    max_i = 2 * M * M + 1
    is_sq = set()
    k = 0
    while k * k <= max_i:
        is_sq.add(k * k)
        k += 1

    count = 0
    for a in range(1, M + 1):
        for b in range(1, M + 1):
            for c in range(1, M + 1):
                gab = g[a][b]
                gbc = g[b][c]
                sum_ac = a + c
                sum_bd_base = b
                for d in range(1, M + 1):
                    boundary = gab + gbc + g[c][d] + g[d][a]
                    twice_area = sum_ac * (b + d)
                    twice_i = twice_area - boundary + 2
                    if twice_i % 2 != 0:
                        continue
                    interior = twice_i // 2
                    if interior in is_sq:
                        count += 1

    print(count)

solve()