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\). Therefore, in triangle \(CBE\),

$$\angle CBE = A.$$

Now apply the sine rule in triangle \(CBE\):

$$\frac{BE}{\sin(C/2)}=\frac{BC}{\sin(A+C/2)}=\frac{a}{\sin(A+C/2)}.$$

So

$$BE=a\cdot\frac{\sin(C/2)}{\sin(A+C/2)}.$$

To simplify the denominator, use \(A+B+C=\pi\):

$$A+\frac{C}{2}=\frac{\pi}{2}+\frac{A-B}{2},$$

hence

$$\sin\!\left(A+\frac C2\right)=\cos\!\left(\frac{A-B}{2}\right).$$

On the other hand, by the sine rule in triangle \(ABC\),

$$a=2R\sin A,\qquad b=2R\sin B,\qquad c=2R\sin C,$$

so

$$a+b=2R(\sin A+\sin B)=4R\cos\!\left(\frac C2\right)\cos\!\left(\frac{A-B}{2}\right),$$

and

$$c=2R\sin C=4R\sin\!\left(\frac C2\right)\cos\!\left(\frac C2\right).$$

Dividing these gives

$$\frac{a+b}{c}=\frac{\cos((A-B)/2)}{\sin(C/2)}=\frac{\sin(A+C/2)}{\sin(C/2)}.$$

Substituting into the previous expression yields the key identity

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

3. The integrality condition becomes pure divisibility

The problem asks when \(BE\) is an integer. Because \(a,b,c\) are integers, the identity above shows that this is equivalent to

$$a+b \mid ac.$$

This is the decisive reduction: the geometric condition disappears completely and the rest of the problem becomes arithmetic counting.

4. For fixed \(a,b\), what values of \(c\) are even possible?

Fix \(a\) and \(b\). Since \(b\le c\) and the triangle inequality requires \(c<a+b\), while the perimeter bound requires \(c\le N-a-b\), the allowed interval is

$$b \le c \le c_{\max},\qquad c_{\max}=\min(a+b-1,\ N-a-b).$$

If \(c_{\max}<b\), then no triangle exists for that pair \((a,b)\).

5. Turning divisibility into an arithmetic progression

Let

$$s=a+b,\qquad g=\gcd(a,b).$$

Because

$$\gcd(a,s)=\gcd(a,a+b)=\gcd(a,b)=g,$$

we may write

$$a=g a_1,\qquad s=g s_1,\qquad \gcd(a_1,s_1)=1.$$

The divisibility condition

$$s\mid ac$$

becomes

$$g s_1 \mid g a_1 c \quad\Longleftrightarrow\quad s_1 \mid a_1 c.$$

Since \(a_1\) and \(s_1\) are coprime, this is equivalent to

$$s_1 \mid c,$$

that is,

$$\frac{s}{g}\mid c.$$

So for fixed \((a,b)\), the valid values of \(c\) form an arithmetic progression with step

$$d=\frac{a+b}{\gcd(a,b)}.$$

6. Closed-form counting for each pair \((a,b)\)

We now only need to count multiples of \(d\) inside the interval \([b,c_{\max}]\). The answer is

$$\left\lfloor\frac{c_{\max}}{d}\right\rfloor-\left\lfloor\frac{b-1}{d}\right\rfloor.$$

This replaces a full inner scan over all \(c\) values by a constant-time formula.

7. Checkpoints and why they matter

The code validates two different parts of the reasoning.

Geometric checkpoint. For sample triangles such as \((3,4,5)\), \((5,5,8)\), \((7,8,9)\), the function be_from_geometry computes \(BE\) directly from coordinates and checks that it matches

$$\frac{ac}{a+b}.$$

Counting checkpoint. For small perimeter limits \(150,300,600\), the fast arithmetic count is compared with a brute-force loop over every admissible \(c\). This confirms that the divisibility reformulation is exact.

How the Code Works

count_range loops over ordered side pairs \((a,b)\), computes \(c_{\max}\), the gcd \(g\), the step \(d=(a+b)/g\), and adds the floor-difference count of multiples of \(d\) in the allowed interval. solve_fast parallelizes only over disjoint ranges of \(a\); mathematically each \((a,b)\) contributes independently. solve_bruteforce is kept only for checkpoint verification.

Complexity Analysis

The outer loops run only over \(a\) and \(b\). Each pair contributes constant-time arithmetic, so the running time is roughly

$$O(N^2),$$

which is a major improvement over the cubic brute-force scan over all \((a,b,c)\). Memory usage is \(O(1)\) apart from thread-local counters.

Further Reading

1. Problem page: https://projecteuler.net/problem=296
2. Angle bisector theorem: https://en.wikipedia.org/wiki/Angle_bisector_theorem
3. Tangent-chord theorem: https://en.wikipedia.org/wiki/Inscribed_angle