Problem 513: Integral Median

Mathematical Foundation

Theorem 1 (Median Diophantine Reduction). The condition $m_a \in \mathbb{Z}^+$ is equivalent to the existence of a positive integer $d$ (with $d = 2m_a$) such that

Proof. $m_a \in \mathbb{Z}^+$ requires $2b^2 + 2c^2 - a^2 = (2m_a)^2 > 0$. Setting $d = 2m_a$, this is $2b^2 + 2c^2 - a^2 = d^2$, which rearranges to $a^2 + d^2 = 2(b^2 + c^2)$. Moreover $d$ must be even (since $d = 2m_a$). $\square$

Lemma 1 (Sum-Difference Substitution). Let $s = b + c$ and $t = c - b$ with $0 \leq t \leq c - b$, $s \equiv t \pmod{2}$. Then the equation becomes

Proof. We have $b^2 + c^2 = \frac{(s-t)^2 + (s+t)^2}{4} = \frac{s^2 + t^2}{2}$. Substituting: $a^2 + d^2 = 2 \cdot \frac{s^2 + t^2}{2} = s^2 + t^2$. $\square$

Theorem 2 (Two-Square Representation Identity). The equation $a^2 + d^2 = s^2 + t^2$ (representing the same integer as a sum of two squares in two ways) can be parametrized using the Brahmagupta—Fibonacci identity via Gaussian integers:

Any two representations of $n = a^2 + d^2 = s^2 + t^2$ arise from different factorizations of $n$ in $\mathbb{Z}[i]$.

Proof. This follows from the unique factorization in $\mathbb{Z}[i]$ (a principal ideal domain) and the norm-multiplicativity $N(\alpha\beta) = N(\alpha)N(\beta)$ where $N(x + yi) = x^2 + y^2$. Distinct representations correspond to grouping the Gaussian prime factors of $n$ differently between $\alpha$ and $\bar{\alpha}$. $\square$

Lemma 2 (Constraint Translation). The triangle inequality $a + b > c$ translates to $a > t = c - b$. The ordering $a \leq b \leq c$ requires $a \leq b = \frac{s-t}{2}$ and $c = \frac{s+t}{2} \leq N$.

Proof. Direct substitution: $a + b > c \Leftrightarrow a > c - b = t$. Also $a \leq b = (s-t)/2$ and $c = (s+t)/2 \leq N$. $\square$

Editorial

Optimized approach:* For each $a$, iterate over valid $m_a$ values and derive $(b, c)$ from the two-square decomposition, or iterate over $(b, c)$ with $b \leq c \leq N$ and check the perfect-square condition on $2b^2 + 2c^2 - a^2$ for $a$ in the valid range. We triangle inequality: a + b > c.

Pseudocode

    Set count <- 0
    For b from 1 to N:
        For c from b to N:
            Set val <- 2 * b^2 + 2 * c^2
            For a from 1 to b:
                Set r <- val - a^2
                If r > 0 and r mod 4 == 0 then
                    Set m <- isqrt(r)
                    If m * m == r then
                        triangle inequality: a + b > c
                        If a + b > c then
                            count += 1
    Return count

Optimized approach: For each $a$, iterate over valid $m_a$ values and derive $(b, c)$ from the two-square decomposition, or iterate over $(b, c)$ with $b \leq c \leq N$ and check the perfect-square condition on $2b^2 + 2c^2 - a^2$ for $a$ in the valid range.

## Complexity Analysis

- **Time:** $O(N^2)$ with the optimized enumeration over $(b, c)$ pairs and $O(1)$ perfect-square check per valid $a$.
- **Space:** $O(N)$ for auxiliary arrays (e.g., precomputed squares).

## Answer

$$
\boxed{2925619196}
$$

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

int main() {
    // Count triangles (a <= b <= c <= N) with integer median m_a
    // m_a = (1/2)*sqrt(2b^2 + 2c^2 - a^2), need this to be a positive integer
    // => 2b^2 + 2c^2 - a^2 = (2m)^2 for some positive integer m

    long long N;
    cout << "Enter N: ";
    cin >> N;

    long long count = 0;
    for (long long b = 1; b <= N; b++) {
        for (long long c = b; c <= N; c++) {
            long long base = 2LL * b * b + 2LL * c * c;
            long long a_min = max(1LL, c - b + 1);
            long long a_max = b;
            for (long long a = a_min; a <= a_max; a++) {
                long long val = base - a * a;
                if (val <= 0) continue;
                long long sq = (long long)sqrt((double)val);
                // Adjust for floating-point errors
                while (sq * sq > val) sq--;
                while ((sq + 1) * (sq + 1) <= val) sq++;
                if (sq * sq == val && sq % 2 == 0) {
                    count++;
                }
            }
        }
    }

    cout << "T(" << N << ") = " << count << endl;
    return 0;
}

"""
Problem 513: Integral Median
A triangle with integer sides a <= b <= c has median to side a:
    m_a = (1/2) * sqrt(2b^2 + 2c^2 - a^2)
Count triangles with a <= b <= c <= N where m_a is a positive integer.
"""

import math

def solve(N: int):
    """
    Count triangles (a, b, c) with a <= b <= c <= N where
    m_a = (1/2)*sqrt(2b^2 + 2c^2 - a^2) is a positive integer.

    We need 2b^2 + 2c^2 - a^2 = 4*m^2 for some positive integer m.
    Equivalently: 2b^2 + 2c^2 - a^2 must be a perfect square of an even number.
    """
    count = 0
    for b in range(1, N + 1):
        for c in range(b, N + 1):
            val_base = 2 * b * b + 2 * c * c
            # a ranges from 1 to b, and triangle inequality: a + b > c => a > c - b
            a_min = max(1, c - b + 1)
            a_max = b
            for a in range(a_min, a_max + 1):
                val = val_base - a * a
                if val <= 0:
                    continue
                sq = math.isqrt(val)
                if sq * sq == val and sq % 2 == 0:
                    count += 1
    return count

def solve_brute_force(N: int):
    """Direct brute-force for small N verification."""
    count = 0
    for a in range(1, N + 1):
        for b in range(a, N + 1):
            for c in range(b, N + 1):
                if a + b <= c:
                    continue
                val = 2 * b * b + 2 * c * c - a * a
                if val > 0:
                    sq = math.isqrt(val)
                    if sq * sq == val and sq % 2 == 0:
                        count += 1
    return count

# Verify on small inputs
N_small = 50
ans1 = solve(N_small)
ans2 = solve_brute_force(N_small)
assert ans1 == ans2, f"Mismatch: {ans1} vs {ans2}"
print(f"T({N_small}) = {ans1}")

# Show growth for moderate N values
Ns = list(range(10, 201, 10))
counts = [solve(n) for n in Ns]
for n, c in zip(Ns, counts):
    print(f"T({n}) = {c}")