Problem 296: Angular Bisector and Tangent

Project Euler Problem 296 Solution

EulerSolve provides an optimized solution for Project Euler Problem 296, Angular Bisector and Tangent, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We are given an integer-sided triangle $ABC$ with $$BC \le AC \le AB.$$ The angle bisector of $\angle ACB$ meets the line through $B$ parallel to the tangent at $C$ to the circumcircle at a point $E$. We must count all triangles with perimeter at most $100000$ for which the segment $BE$ has integer length. Mathematical Approach 1. Side notation used by the code The program uses $$a=BC,\qquad b=CA,\qquad c=AB,$$ so the ordering condition becomes $$a\le b\le c.$$ The triangle inequalities and perimeter bound then force $$c < a+b,\qquad a+b+c\le N.$$ 2. A clean trigonometric derivation of $BE$ Let the angles of triangle $ABC$ be $A,B,C$ at the corresponding vertices. Because $CE$ is the angle bisector of $\angle C$, we have $$\angle ECB=\frac{C}{2}.$$ The line through $B$ is parallel to the tangent at $C$ to the circumcircle. By the tangent-chord theorem, the angle between that tangent and the chord $CB$ equals the angle at $A$....

Detailed mathematical approach

Problem Summary

We are given a triangle $ABC$ with integer side lengths and $BC\le AC\le AB$. The line $k$ bisects the angle $ACB$, the line $m$ is the tangent at $C$ to the circumscribed circle of the triangle, and $n$ is the line through $B$ parallel to $m$. The lines $n$ and $k$ meet at a point $E$. We must count the triangles with perimeter at most $100\,000$ for which the segment $BE$ has integer length. ^[1] Congruent triangles count once: a triangle is determined by its three side lengths, and the order $BC\le AC\le AB$ fixes which side is which, so we count triples of side lengths. The statement gives no smaller example; Section 11 counts the $15$ triangles with perimeter at most $25$ by hand.

The whole solution in one sentence: the point $E$ is exactly as far from $B$ as the point where the bisector meets the side $AB$, which makes $BE$ a simple fraction of the side lengths, and the triangles in which this fraction is an integer can be counted with a few divisions for each pair of shorter sides.

Mathematical Approach

Sections 1–6 turn the length $BE$ into a simple fraction of the side lengths, Sections 7–9 turn the condition that $BE$ is an integer into a divisibility condition, and Sections 10–12 count the triangles that satisfy it.

1. Sides, angles and the conditions

We write $a=BC$, $b=CA$ and $c=AB$ for the sides, $\alpha$, $\beta$, $\gamma$ for the angles at $A$, $B$ and $C$, so that $\alpha+\beta+\gamma=\pi$, and $(a,b,c)$ for the triangle. Three positive integers are the sides of a triangle exactly when each of them is smaller than the sum of the other two. For $a\le b\le c$ the conditions $a\lt b+c$ and $b\lt a+c$ hold automatically, so only $c\lt a+b$ remains, and with the perimeter bound $N=100\,000$ the triples to be examined are

$$a\le b\le c\le a+b-1,\qquad a+b+c\le N.$$

2. A symmetric warm-up

Suppose first that $a=b$. The vertex $C$ and the centre $O$ of the circumscribed circle are both as far from $A$ as from $B$, so both lie on the perpendicular bisector of $AB$. Reflection in that line swaps $A$ and $B$ and fixes $C$, so the line is the bisector $k$. The tangent at $C$ is perpendicular to the radius $OC$, ^[2] that is, to $k$, and so is $AB$. Hence $m$ is parallel to $AB$, the parallel $n$ through $B$ is the line $AB$ itself, and $E$ is the midpoint of $AB$: $BE=c/2$. For $a=b$ the length $BE$ is therefore an integer exactly when $c$ is even. The triangle $(2,2,2)$ has $BE=1$ and $(3,3,4)$ has $BE=2$, while $(3,3,5)$ has $BE=5/2$.

3. The tangent fixes the angle at B

Now let the triangle be arbitrary. The tangent–chord theorem, also called the alternate segment theorem, says that the angle between the tangent at $C$ and the chord $CB$ equals the angle that the chord subtends at the points of the circle on the other side of it, here at $A$. ^[2] So if $T$ is a point of $m$ on the other side of the line $CB$ than $A$, then $\angle TCB=\alpha$. The line $CB$ crosses the parallel lines $m$ and $n$, and alternate angles at such a crossing are equal, ^[3] so the ray of $n$ that leaves $B$ on the side of $A$ makes the angle $\alpha$ with $BC$. The bisector leaves $C$ on the same side at the angle $\gamma/2$ with $CB$. Since $\alpha+\gamma/2\lt\pi$, the two rays meet, ^[3] and their meeting point is $E$. The triangle $CBE$ therefore has the angles $\gamma/2$ at $C$ and $\alpha$ at $B$, and so $\pi-\alpha-\gamma/2=\beta+\gamma/2$ at $E$.

4. BE is as long as BD

Let $D$ be the point where the bisector $k$ meets the side $AB$. The triangle $CBD$ has the angles $\gamma/2$ at $C$ and $\beta$ at $B$, hence $\alpha+\gamma/2$ at $D$. In both triangles $CBE$ and $CBD$ the side $BC=a$ lies opposite the angle at $E$ or $D$, and the side $BE$ or $BD$ opposite the angle $\gamma/2$ at $C$. The law of sines, $a/\sin\alpha=b/\sin\beta=c/\sin\gamma$ in every triangle, ^[4] therefore gives

$$\begin{aligned}BE&=\frac{a\sin(\gamma/2)}{\sin(\beta+\gamma/2)},\\[4pt] BD&=\frac{a\sin(\gamma/2)}{\sin(\alpha+\gamma/2)}.\end{aligned}$$

The angles $\beta+\gamma/2$ and $\alpha+\gamma/2$ add up to $\alpha+\beta+\gamma=\pi$, and $\sin(\pi-\theta)=\sin\theta$, so the two denominators are equal and $BE=BD$. There is a picture behind this. If $a\lt b$, then $\alpha\lt\beta$, because the larger side lies opposite the larger angle; the ray $BE$ then lies inside the angle $CBD$, so $E$ lies between $C$ and $D$, and the triangle $BDE$ has the angle $\alpha+\gamma/2$ at $D$ and the same angle $\pi-(\beta+\gamma/2)$ at $E$: it is isosceles with apex $B$. If $a=b$, the points $E$ and $D$ coincide, as in Section 2.

5. The bisector cuts AB in the ratio of the sides

The angle bisector theorem says that the bisector of an angle of a triangle divides the opposite side in the ratio of the two adjacent sides, ^[5] here $AD:DB=CA:CB=b:a$. Together with $AD+DB=c$ this gives $DB=ac/(a+b)$, and with Section 4

$$BE=BD=\frac{ac}{a+b}.$$

For $a=b$ this is $c/2$, as in Section 2. Sections 3–5 never used the order of the sides, so the formula holds for every triangle.

6. Worked example: the 3-4-5 triangle

Take $a=3$, $b=4$, $c=5$ and put $C=(0,0)$, $B=(3,0)$, $A=(0,4)$. The point $O=(3/2,2)$ is at distance $5/2$ from all three vertices, so it is the centre of the circumscribed circle. The tangent $m$ at $C$ is perpendicular to $OC$, so it is the line $3x+4y=0$; its parallel through $B$ is $n\colon 3x+4y=9$, and the bisector of the right angle at $C$ is $k\colon y=x$. They meet at $E=(9/7,9/7)$, so

$$BE^2=\Bigl(\frac{12}{7}\Bigr)^2+\Bigl(\frac{9}{7}\Bigr)^2=\frac{225}{49}.$$

Hence $BE=15/7$. The side $AB$ lies on the line $4x+3y=12$, which meets $k$ at $D=(12/7,12/7)$, so $BD=15/7$ and $AD=20/7$, in the ratio $AD:DB=4:3=b:a$, and $E$ lies between $C$ and $D$. The formula gives $ac/(a+b)=15/7$ as well. This is not an integer, so the 3-4-5 triangle is not counted.

7. When BE is an integer

Since $BE=ac/(a+b)$ with integers $a$, $b$ and $c$, the length is an integer exactly when $a+b$ divides $ac$:

$$BE\in\mathbb Z\iff (a+b)\mid ac.$$

The geometry has disappeared, and only a question about integers remains. For $(6,9,10)$ we get $ac=60=4\cdot15$, so $BE=4$; for $(6,9,11)$ the product $66$ is not a multiple of $15$.

8. Removing the common factor

Let $g=\gcd(a,b)$ be the greatest common divisor of $a$ and $b$, the largest integer that divides both; two numbers whose greatest common divisor is $1$ are called coprime. A number divides both $a$ and $a+b$ exactly when it divides both $a$ and $b$, because $b=(a+b)-a$; hence $\gcd(a,a+b)=g$, the rule on which the subtraction form of the Euclidean algorithm rests. ^[6] Write $a=ga'$ and $a+b=gs'$, so that $\gcd(a',s')=1$. Then $(a+b)\mid ac$ means $gs'\mid ga'c$, that is $s'\mid a'c$, and since $s'$ is coprime to $a'$, Euclid's lemma gives $s'\mid c$. ^[7] Conversely, $s'\mid c$ implies $gs'\mid ga'c$. Therefore

$$(a+b)\mid ac\iff d\mid c,\qquad d=\frac{a+b}{\gcd(a,b)}.$$

For $a=4$ and $b=8$ we get $g=4$ and $d=3$: of the possible sides $c=8,9,10,11$ only $c=9$ is a multiple of $3$, and indeed $4\cdot9=36=3\cdot12$.

9. What the counted triangles look like

Write $a=gx$ and $b=gy$ with $\gcd(x,y)=1$ and $x\le y$; then $a+b=g(x+y)$ and $d=x+y$. The triangle inequality $c\lt a+b=gd$ leaves only the multiples $c=jd$ with $1\le j\le g-1$, so a pair without a common factor, $g=1$, never contributes. Every counted triangle has the form

$$a=gx,\quad b=gy,\quad c=j(x+y),\quad BE=jx,$$

with $1\le j\le g-1$, $j(x+y)\ge gy$ (because $c\ge b$) and $(g+j)(x+y)\le N$ (the perimeter). The case $x=y=1$ gives the triangles $(g,g,2j)$ of Section 2; $x=1$, $y=2$, $g=4$, $j=3$ gives $(4,8,9)$ with $BE=3$; and $x=2$, $y=3$, $g=3$, $j=2$ gives $(6,9,10)$ with $BE=4$. Pairs without a common factor are the majority: the proportion of coprime pairs among all pairs of numbers up to $N$ tends to $6/\pi^2\approx0.61$ as $N$ grows, ^[8] and among the pairs $(a,b)$ that the program visits for $N=100\,000$ it is $0.6079$. Conversely, any such $x$, $y$, $g$, $j$ give a triangle with integer $BE=jx$, and different choices give different triangles, because $g=\gcd(a,b)$, $x=a/g$, $y=b/g$ and $j=c/(x+y)$ are determined by the triangle. The published programs do not use this description; the independent check under Complexity and Verification does.

10. Counting the multiples in a window

For fixed $a$ and $b$ the side $c$ runs through the window $b\le c\le c_{\max}$ with $c_{\max}=\min(a+b-1,N-a-b)$. The multiples of $d$ among $1,2,\dots,n$ are $d,2d,\dots,\lfloor n/d\rfloor d$, where $\lfloor x\rfloor$ is the largest integer not exceeding $x$, ^[9] so there are $\lfloor n/d\rfloor$ of them. Removing the multiples below $b$ leaves

$$Q(a,b)=\Bigl\lfloor\frac{c_{\max}}{d}\Bigr\rfloor-\Bigl\lfloor\frac{b-1}{d}\Bigr\rfloor$$

triangles for the pair $(a,b)$. A whole window costs two divisions instead of a scan over $c$.

11. Worked example: perimeter at most 25

For $N=25$ the loops of Section 12 visit $52$ pairs $(a,b)$, and $33$ of them are coprime and contribute nothing. The seven pairs $a=b=g$ with $2\le g\le8$ have $d=2$, so they count the even $c$ of their windows; for $g=6$ the window is $6\le c\le11$ and $Q(6,6)=\lfloor11/2\rfloor-\lfloor5/2\rfloor=3$, the sides $c=6,8,10$. For $g=2,3,\dots,8$ the counts are $1,1,2,2,3,2,1$, together $12$ triangles. Of the remaining twelve pairs with a common factor only three contribute: $(3,6)$ with $d=3$ and the window $6\le c\le8$ gives $c=6$; $(4,8)$ with $d=3$ and the window $8\le c\le11$ gives $c=9$; $(6,9)$ with $d=5$ and the window $9\le c\le10$ gives $c=10$. A pair such as $(4,10)$, with $d=7$ and the window $10\le c\le11$, finds no multiple. So there are $15$ triangles with perimeter at most $25$: the twelve with $a=b$, and $(3,6,6)$, $(4,8,9)$ and $(6,9,10)$ with $BE=2$, $3$ and $4$.

12. Every triangle is counted exactly once

From $a\le b\le c$ we get $3a\le a+b+c\le N$ and $2b\le b+c\le N-a$, so $a$ runs from $1$ to $\lfloor N/3\rfloor$ and $b$ from $a$ to $\lfloor(N-a)/2\rfloor$. For each of these pairs the window of Section 10 is not empty: $a+b-1\ge b$ because $a\ge1$, and $N-a-b\ge b$ because $2b\le N-a$. Every triangle has exactly one triple $(a,b,c)$, its side $c$ lies in the window of its pair, and by Sections 5, 7, 8 and 10 it is counted exactly when $BE$ is an integer. The number we want is therefore

$$\sum_{a=1}^{\lfloor N/3\rfloor}\ \sum_{b=a}^{\lfloor (N-a)/2\rfloor}Q(a,b).$$

How the Code Works

The C++ program ^[10] starts in main: parse_arguments reads the options --limit= (default $100\,000$) and --skip-checkpoints and rejects unknown arguments and limits below $3$. Unless told to skip them, run_checkpoints runs first; if a check fails, the program stops with exit status $2$ and prints no count. Then solve_fast evaluates the double sum of Section 12 and the program prints it.

count_range(limit, a_start, a_end) implements Sections 10 and 12 literally. For each $a$ of its range and each $b$ from $a$ to (limit - a) / 2 it sets $s=a+b$ and c_max $=\min(s-1,\,N-s)$, takes g = std::gcd(a, b) and the step $s/g=d$ of Section 8, and adds c_max / step - (b - 1) / step to a 64-bit unsigned total; division of non-negative integers in C++ rounds down, so these are the floors of Section 10. The test c_max < b is a safety check that never fires, by Section 12. solve_fast calls count_range once for the whole range $1\le a\le\lfloor N/3\rfloor$ when $\lfloor N/3\rfloor\lt5000$ or when a single piece is requested; otherwise it cuts this range into consecutive pieces of equal length, except possibly the last, counts each piece with count_range and adds the partial counts. The total is the same, because every pair $(a,b)$ lies in exactly one piece.

run_checkpoints tests the geometry and the counting separately. be_from_geometry(a, b, c) computes $BE$ without the formula: it puts $C$ at the origin and $A=(b,0)$ on the $x$-axis, finds $B$ below the axis from its distances $a$ to $C$ and $c$ to $A$, takes the sum $u$ of the unit vectors along $CA$ and $CB$ as the direction of $k$, finds the centre $O=(b/2,o_y)$ from $|OB|=|OC|$ and the direction $w$ perpendicular to $OC$ of $m$ and $n$, solves $C+su=B+tw$ by Cramer's rule and returns $|t|\,|w|$. For the five triangles $(3,4,5)$, $(5,5,8)$, $(7,8,9)$, $(9,12,14)$ and $(11,13,15)$ this must agree with $ac/(a+b)$ to within $10^{-9}$; the second and the fourth have integer lengths $BE=4$ and $BE=6$. Then, for $N=150$, $300$ and $600$, solve_fast(limit, 1), which counts in a single piece, must agree with solve_bruteforce, the triple loop over all triangles that tests $ac\equiv0\pmod{a+b}$ directly with a 64-bit product; both give $924$, $4359$ and $20107$. The geometry calculation uses long double, which with GCC on x86 is the 80-bit extended format but on 64-bit ARM under macOS is the same as double; ^[11] even in double precision be_from_geometry agrees with the formula to within $3\cdot10^{-14}$ for every triangle with perimeter at most $300$, far inside the tolerance.

The Java program contains the same countRange with its own Euclidean gcd loop, int arithmetic and a long total. It has the limit $100\,000$ built in, takes no options and runs no checkpoints; it also cuts the range of $a$ into consecutive pieces and adds their counts. If collecting a partial count throws an exception, the program prints the stack trace and carries on, so the printed total would lack that piece and the run would still end normally; normal runs raise none. The Python file is a bridge: it compiles the C++ source Euler296.cpp from the neighbouring folder solutionsCpp with clang++ or g++ (options -std=c++17 -O2) whenever the binary is missing or older than the source, runs it without arguments, so that the checkpoints run first, and returns the printed number; a failed checkpoint makes the call raise an error.

Complexity and Verification

count_range visits every pair $(a,b)$ of Section 12 once, that is

$$\sum_{a=1}^{\lfloor N/3\rfloor}\Bigl(\Bigl\lfloor\frac{N-a}{2}\Bigr\rfloor-a+1\Bigr)\approx\frac{N^2}{12}$$

pairs, exactly $833\,333\,333$ for $N=100\,000$, and spends one gcd and three divisions on each: the step $s/g$ and the two floors of Section 10. A gcd takes $O(\log N)$ steps: by Lamé's theorem, the Euclidean algorithm started with the larger number needs at most five division steps per decimal digit of the smaller number, ^[6] and the Java loop, which receives the smaller number first, needs at most one step more. The time is therefore $O(N^2\log N)$, and the memory is a handful of integers plus one partial count per piece. In our runs each of the three programs finished within a few seconds. In the fast loops all numbers are at most $N$, so 32-bit integers suffice; the running total has 64 bits and cannot exceed the number of all triangles with perimeter at most $N$, which is far below $2^{63}$. That number also shows why the triple loop of solve_bruteforce serves only as a check: the number of integer triangles with perimeter exactly $n$ is the integer nearest to $n^2/48$ for even $n$ and to $(n+3)^2/48$ for odd $n$, ^[12] so about $N^3/144$ triangles have perimeter at most $N$, exactly $6\,944\,861\,111\,111$ for $N=100\,000$.

Besides the checkpoints of the C++ program, the following was verified for this article:

A separate coordinate computation with $50$-digit arithmetic, which puts $B$ at the origin and $C$ on the $x$-axis, intersects $n$ and $k$ for each of the $191\,250$ triangles with perimeter at most $300$. It confirms $BE=BD=ac/(a+b)$ to within $10^{-48}$, finds $E$ strictly between $C$ and $D$ whenever $a\lt b$ and $E=D$ whenever $a=b$, and finds an integer $BE$ for exactly $4359$ triangles, the count of the formula.
For every $N$ from $3$ to $600$ the triple-loop brute force, a Python transcription of count_range and the C++ program run with --limit= give the same count, for example $1$, $2$, $9$, $25$, $77$ and $376$ for $N=6$, $10$, $20$, $30$, $50$ and $100$.
A separately written program that enumerates the coprime pairs $(x,y)$ and the numbers $g$ and $j$ of Section 9 instead of the pairs $(a,b)$ agrees with the C++ program for every $N$ from $3$ to $3000$, for twelve larger limits up to $50\,000$ and for $N=100\,000$; for $N=1000$ both give $61339$.
The C++ program built with Clang and with GCC, the Java program and the Python bridge print the same value for $N=100\,000$.

Footnotes and References

The references below supply the background facts used above. The formula $BE=BD=ac/(a+b)$, the reduction to the multiples of $(a+b)/\gcd(a,b)$, the description of the counted triangles and all counts are derived explicitly in this article.

Project Euler 296 — Angular Bisector and Tangent. The official statement takes an integer-sided triangle ABC with BC ≤ AC ≤ AB, the bisector k of the angle ACB, the tangent m at C to the circumscribed circle and the line n through B parallel to m, calls the intersection of n and k the point E, and asks how many such triangles with perimeter not exceeding 100 000 have a segment BE of integral length.
Wikipedia — Tangent lines to circles. Every tangent line to a circle is perpendicular to the radius at the point of contact. By the tangent–chord theorem, also called the alternate segment theorem, the angle between a chord and a tangent at one of its ends is half the central angle of the chord and equals the inscribed angle of the chord in the alternate segment.
Wikipedia — Transversal (geometry). When a transversal crosses two parallel lines, the two angles of each pair of alternate angles are congruent (Euclid, Elements I.29); and if the interior angles on one side of a transversal add up to less than two right angles, the two lines intersect, which is Euclid's parallel postulate.
Wikipedia — Law of sines. In every triangle a/sin α = b/sin β = c/sin γ = 2R, where α, β and γ are the angles opposite the sides a, b and c, and R is the radius of the circumscribed circle.
Wikipedia — Angle bisector theorem. If the bisector of the angle at A of a triangle ABC meets BC at D, then BD : CD = AB : AC. With the vertices renamed, the bisector from C divides AB in the ratio AD : DB = CA : CB used in Section 5.
Wikipedia — Euclidean algorithm. The greatest common divisor of two numbers does not change when the larger number is replaced by its difference with the smaller one. For a pair a > b, whose first step divides a by b with remainder, a theorem of Lamé (1844) bounds the number of steps by five times the number of decimal digits of the smaller number b.
Wikipedia — Euclid's lemma. In its general form: if an integer n divides a product ab and is coprime to a, then n divides b. The article proves this with Bézout's identity.
Wikipedia — Coprime integers. In the section on the probability of coprimality: the probability that two integers chosen at random from 1, …, N are coprime tends to 6/π², about 61%, as N grows.
Wikipedia — Floor and ceiling functions. The floor ⌊x⌋ is the greatest integer less than or equal to x. Section 10 uses it to count the multiples of d among 1, …, n.
C++ — Euler296.cpp. The linked immutable C++ revision contains be_from_geometry, count_range, solve_fast, solve_bruteforce and run_checkpoints with the five test triangles and the limits 150, 300 and 600. It is the implementation record for this article.
Wikipedia — Long double. Most C compilers for x86 implement long double as the 80-bit extended precision type of the hardware, while on 32-bit ARM and on 64-bit ARM under Windows and macOS long double is simply a synonym for double.
OEIS A005044 — Alcuin's sequence. Its n-th term is the number of triangles with integer sides and perimeter n, and it equals round(n²/48) for even n and round((n + 3)²/48) for odd n; adding these terms up to N gives the count of about N³/144 triangles used above.

Problem 296 source code

C++

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>
#include <thread>
#include <vector>

namespace {

using u64 = std::uint64_t;
using i64 = std::int64_t;

struct Options {
    int limit = 100000;
    unsigned threads = std::thread::hardware_concurrency();
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_unsigned_after_prefix(const std::string& arg, const std::string& prefix, unsigned& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    unsigned parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10U + static_cast<unsigned>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        if (parse_unsigned_after_prefix(arg, "--threads=", options.threads)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    if (options.limit < 3) {
        return false;
    }
    if (options.threads == 0) {
        options.threads = 1;
    }
    return true;
}

long double be_from_geometry(const int a, const int b, const int c) {
    // C=(0,0), A=(b,0), B determined by side lengths.
    const long double bx = (static_cast<long double>(a) * a + static_cast<long double>(b) * b -
                            static_cast<long double>(c) * c) /
                           (2.0L * b);
    const long double by2 = static_cast<long double>(a) * a - bx * bx;
    const long double by = -std::sqrt(std::max(0.0L, by2));

    // Angle bisector at C points along unit(CA)+unit(CB).
    const long double ux = 1.0L + bx / a;
    const long double uy = by / a;

    // Tangent at C to circumcircle is perpendicular to OC.
    // Circumcenter O satisfies OA=OC and OB=OC.
    // With C at origin and A on x-axis: O=(b/2, oy).
    const long double oy =
        (bx * bx + by * by - b * bx) / (2.0L * by);  // from OB^2 = OC^2.
    const long double ox = b / 2.0L;

    // Tangent direction is perpendicular to O vector.
    const long double tx = -oy;
    const long double ty = ox;

    // Solve C + s*u = B + t*tangent, then BE = |t|*|tangent|.
    const long double det = ux * (-ty) - uy * (-tx);
    const long double rhsx = bx;
    const long double rhsy = by;

    const long double t = (ux * rhsy - uy * rhsx) / det;
    const long double tangent_len = std::sqrt(tx * tx + ty * ty);
    return std::fabsl(t) * tangent_len;
}

u64 count_range(const int limit, const int a_start, const int a_end) {
    u64 total = 0;

    for (int a = a_start; a <= a_end; ++a) {
        const int b_max = (limit - a) / 2;
        for (int b = a; b <= b_max; ++b) {
            const int s = a + b;
            const int c_max = std::min(s - 1, limit - s);
            if (c_max < b) {
                continue;
            }

            const int g = std::gcd(a, b);
            const int step = s / g;
            total += static_cast<u64>(c_max / step - (b - 1) / step);
        }
    }

    return total;
}

u64 solve_fast(const int limit, unsigned threads) {
    const int a_max = limit / 3;
    if (threads <= 1 || a_max < 5000) {
        return count_range(limit, 1, a_max);
    }

    const unsigned use_threads = std::min<unsigned>(threads, static_cast<unsigned>(a_max));
    const int chunk = (a_max + static_cast<int>(use_threads) - 1) / static_cast<int>(use_threads);

    std::vector<std::thread> pool;
    std::vector<u64> partial(use_threads, 0);
    pool.reserve(use_threads);

    for (unsigned t = 0; t < use_threads; ++t) {
        const int start = static_cast<int>(t) * chunk + 1;
        const int end = std::min(a_max, start + chunk - 1);
        if (start > end) {
            continue;
        }
        pool.emplace_back([&, start, end, t]() {
            partial[t] = count_range(limit, start, end);
        });
    }

    for (auto& th : pool) {
        th.join();
    }

    u64 total = 0;
    for (u64 part : partial) {
        total += part;
    }
    return total;
}

u64 solve_bruteforce(const int limit) {
    u64 total = 0;
    for (int a = 1; a <= limit / 3; ++a) {
        for (int b = a; b <= (limit - a) / 2; ++b) {
            const int c_max = std::min(a + b - 1, limit - a - b);
            for (int c = b; c <= c_max; ++c) {
                if ((static_cast<i64>(a) * c) % (a + b) == 0) {
                    ++total;
                }
            }
        }
    }
    return total;
}

bool run_checkpoints() {
    {
        // Geometry validation for the BE formula on a few integer triangles.
        struct Tri {
            int a;
            int b;
            int c;
        };
        const std::vector<Tri> tests = {
            {3, 4, 5},
            {5, 5, 8},
            {7, 8, 9},
            {9, 12, 14},
            {11, 13, 15},
        };

        for (const auto& tri : tests) {
            const long double be_geom = be_from_geometry(tri.a, tri.b, tri.c);
            const long double be_formula =
                static_cast<long double>(tri.a) * tri.c / static_cast<long double>(tri.a + tri.b);
            if (std::fabsl(be_geom - be_formula) > 1e-9L) {
                std::cerr << "Geometry checkpoint failed for (" << tri.a << ',' << tri.b << ','
                          << tri.c << ")" << '\n';
                return false;
            }
        }
    }

    for (int limit : {150, 300, 600}) {
        const u64 fast = solve_fast(limit, 1);
        const u64 brute = solve_bruteforce(limit);
        if (fast != brute) {
            std::cerr << "Counting checkpoint failed for limit=" << limit << ": fast=" << fast
                      << ", brute=" << brute << '\n';
            return false;
        }
    }

    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }

    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    const u64 answer = solve_fast(options.limit, options.threads);
    std::cout << answer << '\n';
    return 0;
}

Python

from __future__ import annotations

import re
import shutil
import subprocess
from pathlib import Path

ANSWER_RE = re.compile(r"answer\s*:\s*(.+)$", re.IGNORECASE)
EQUAL_RE = re.compile(r"=\s*(.+)$")


def parse_output(stdout: str) -> str:
    lines = [line.strip() for line in stdout.splitlines() if line.strip()]
    if not lines:
        return ""

    answer_candidates = []
    equal_candidates = []
    for line in lines:
        m1 = ANSWER_RE.search(line)
        if m1:
            answer_candidates.append(m1.group(1).strip())
        m2 = EQUAL_RE.search(line)
        if m2:
            equal_candidates.append(m2.group(1).strip())

    if answer_candidates:
        return answer_candidates[-1]
    if equal_candidates:
        return equal_candidates[-1]
    return lines[-1]


def solve() -> str:
    problem_id = __file__.split("Euler")[-1].split(".")[0]
    root = Path(__file__).resolve().parent.parent
    src = root / "solutionsCpp" / f"Euler{problem_id}.cpp"
    binary = root / "solutionsCpp" / f".euler{problem_id}_py_bridge"

    if not binary.exists() or src.stat().st_mtime > binary.stat().st_mtime:
        compiler = shutil.which("clang++") or shutil.which("g++")
        if not compiler:
            raise RuntimeError("No C++ compiler found (clang++/g++).")
        subprocess.check_call([compiler, "-std=c++17", "-O2", str(src), "-o", str(binary)])

    output = subprocess.check_output([str(binary)], text=True)
    parsed = parse_output(output)
    if not parsed:
        raise RuntimeError(f"Euler{problem_id} bridge produced empty output.")
    return parsed


if __name__ == "__main__":
    print(solve())

Java

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Euler296 {
    static int gcd(int a, int b) {
        while (b != 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static long countRange(int limit, int aStart, int aEnd) {
        long total = 0;
        for (int a = aStart; a <= aEnd; ++a) {
            int bMax = (limit - a) / 2;
            for (int b = a; b <= bMax; ++b) {
                int s = a + b;
                int cMax = Math.min(s - 1, limit - s);
                if (cMax < b)
                    continue;

                int g = gcd(a, b);
                int step = s / g;
                total += (cMax / step) - ((b - 1) / step);
            }
        }
        return total;
    }

    public static String solve() {
        int limit = 100000;
        int aMax = limit / 3;
        int threads = Runtime.getRuntime().availableProcessors();
        if (threads <= 1) {
            return String.valueOf(countRange(limit, 1, aMax));
        }

        int useThreads = Math.min(threads, aMax);
        int chunk = (aMax + useThreads - 1) / useThreads;

        ExecutorService executor = Executors.newFixedThreadPool(useThreads);
        List<Future<Long>> futures = new ArrayList<>();

        for (int t = 0; t < useThreads; ++t) {
            final int start = t * chunk + 1;
            final int end = Math.min(aMax, start + chunk - 1);
            if (start > end)
                continue;

            futures.add(executor.submit(() -> countRange(limit, start, end)));
        }

        long total = 0;
        for (Future<Long> f : futures) {
            try {
                total += f.get();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        executor.shutdown();

        return String.valueOf(total);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}