Problem 296: Angular Bisector and Tangent

Mathematical Foundation

Theorem 1 (Formula for $BE$). Let $a = BC$, $b = AC$, $c = AB$ with $a \leq b \leq c$. Then

Proof. By the tangent-chord angle theorem (also known as the inscribed angle theorem for tangent lines), the angle between the tangent $m$ at $C$ and the chord $CA$ equals the inscribed angle $\angle ABC = \beta$, and the angle between $m$ and chord $CB$ equals $\angle BAC = \alpha$.

Let $\gamma = \angle ACB$. The bisector $k$ bisects $\gamma$, making angles $\gamma/2$ with both $CA$ and $CB$. The line $n$ through $B$ is parallel to $m$.

In triangle $BCE$, since $n \parallel m$, the angle $\angle EBC = \angle$ between $n$ and $BC$ equals the angle between $m$ and $BC = \alpha$ (alternate interior angles with the transversal $BC$… more precisely, corresponding angles via the parallel). The bisector $k$ from $C$ makes angle $\gamma/2$ with $CB$.

Applying the sine rule in triangle $BCE$:

Since the angles of triangle $BCE$ sum to $\pi$, and using $\angle EBC = \alpha$, $\angle BCE = \gamma/2$, we get $\angle BEC = \pi - \alpha - \gamma/2$. By the sine rule in the original triangle, $\frac{a}{\sin \alpha} = \frac{b}{\sin \beta} = \frac{c}{\sin \gamma}$, and after algebraic manipulation (using $\alpha + \beta + \gamma = \pi$ and the identity $\sin \gamma = 2 \sin(\gamma/2)\cos(\gamma/2)$), one obtains:

Theorem 2 (Integrality Condition). Let $g = \gcd(a, b)$, $a = g a'$, $b = g b'$ with $\gcd(a', b') = 1$. Then $BE \in \mathbb{Z}$ if and only if $(a' + b') \mid c$.

Proof. We have $BE = \frac{ca}{a+b} = \frac{c \cdot ga'}{g(a'+b')} = \frac{ca'}{a'+b'}$. Since $\gcd(a', b') = 1$, we have $\gcd(a', a'+b') = \gcd(a', b') = 1$. Therefore $(a'+b') \mid c a'$ if and only if $(a'+b') \mid c$. $\square$

Lemma 1 (Parametric Constraints). Writing $c = k(a'+b')$ for some positive integer $k$, the constraints are:

1. Ordering: $a \leq b$ gives $a' \leq b'$; $b \leq c$ gives $gb' \leq k(a'+b')$.
2. Triangle inequality: $a + b > c$ gives $g(a'+b') > k(a'+b')$, hence $k < g$.
3. Perimeter: $(g+k)(a'+b') \leq 100{,}000$.

Proof. Substituting $a = ga'$, $b = gb'$, $c = k(a'+b')$:

• $a \leq b \iff a' \leq b'$ (since $g > 0$).
• $b \leq c \iff gb' \leq k(a'+b')$, i.e., $k \geq \lceil gb'/(a'+b') \rceil$.
• $a + b > c \iff g(a'+b') > k(a'+b') \iff g > k$.
• Perimeter $= ga' + gb' + k(a'+b') = (g+k)(a'+b') \leq 100{,}000$. $\square$

Editorial

Triangle ABC with integer sides a=BC <= b=AC <= c=AB, perimeter <= 100000. BE = ca / (a+b) must be a positive integer. With g = gcd(a,b), a = ga’, b = gb’, gcd(a’,b’)=1: BE = ca’/(a’+b’), so (a’+b’) | c, i.e., c = k*(a’+b’). Constraints: a’ <= b’ (from a <= b) k >= ceil(gb’/(a’+b’)) (from b <= c) k < g (from triangle inequality a+b > c) (g+k)(a’+b’) <= P (perimeter). We enumerate coprime pairs (a’, b’) with 1 <= a’ <= b’. Finally, iterate over each g: k ranges from ceil(g*b’/s) to min(g-1, floor(P/s) - g).

Pseudocode

Enumerate coprime pairs (a', b') with 1 <= a' <= b'
For each g: k ranges from ceil(g*b'/s) to min(g-1, floor(P/s) - g)

Complexity Analysis

• Time: $O\!\left(\sum_{\substack{1 \leq a' \leq b' \\ \gcd(a',b')=1}} \frac{P}{a'+b'}\right) = O(P \cdot H)$ where $H = \sum_{s=2}^{P} \frac{\phi_{\text{pairs}}(s)}{s}$ and $\phi_{\text{pairs}}(s)$ counts coprime pairs summing to $s$. By standard estimates this is $O(P \log P)$.
• Space: $O(1)$ working memory (no auxiliary data structures beyond loop variables).

Answer

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

// Problem 296: Angular Bisector and Tangent
//
// Triangle ABC with integer sides a=BC <= b=AC <= c=AB, perimeter <= 100000.
// BE = c*a / (a+b) must be a positive integer.
//
// Let g = gcd(a,b), a = g*a', b = g*b', gcd(a',b')=1.
// Then BE = c*a'/(a'+b'), and since gcd(a',a'+b')=1, we need (a'+b') | c.
// So c = k*(a'+b') for positive integer k.
//
// Constraints:
//   a <= b:          a' <= b'
//   b <= c:          g*b' <= k*(a'+b')  =>  k >= ceil(g*b'/(a'+b'))
//   a+b > c:         g*(a'+b') > k*(a'+b')  =>  k < g
//   perimeter <= P:  (g+k)*(a'+b') <= P

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    const long long P = 100000;
    long long count = 0;

    // Iterate over coprime (a', b') with 1 <= a' <= b'
    // s = a' + b', s ranges from 2 (a'=b'=1) upward
    // Need (g+k)*s <= P, g >= 2 (since k >= 1, k < g => g >= 2), so s <= P/2

    for (long long bp = 1; bp * 2 + 1 <= P; bp++) {
        // a' ranges from 1 to b'
        for (long long ap = 1; ap <= bp; ap++) {
            if (__gcd(ap, bp) != 1) continue;

            long long s = ap + bp;
            // g ranges from 2 to floor(P/s) - 1 (need k >= 1, so g+1 <= P/s => g <= P/s - 1)
            // Also k < g and k >= ceil(g*b'/s)
            long long max_gs = P / s; // (g+k)*s <= P, g+k <= P/s

            for (long long g = 2; g <= max_gs - 1; g++) {
                // k >= ceil(g*b'/s), k < g, g+k <= P/s => k <= P/s - g
                long long k_min = (g * bp + s - 1) / s; // ceil(g*bp/s)
                long long k_max = min(g - 1, max_gs - g);

                if (k_min > k_max) continue;
                count += k_max - k_min + 1;
            }
        }
    }

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

"""
Project Euler Problem 296: Angular Bisector and Tangent

Triangle ABC with integer sides a=BC <= b=AC <= c=AB, perimeter <= 100000.
BE = c*a / (a+b) must be a positive integer.

With g = gcd(a,b), a = g*a', b = g*b', gcd(a',b')=1:
  BE = c*a'/(a'+b'), so (a'+b') | c, i.e., c = k*(a'+b').

Constraints:
  a' <= b' (from a <= b)
  k >= ceil(g*b'/(a'+b'))  (from b <= c)
  k < g  (from triangle inequality a+b > c)
  (g+k)*(a'+b') <= P  (perimeter)
"""
from math import gcd

def solve():
    P = 100000
    count = 0

    for bp in range(1, P // 2 + 1):
        if (bp + 1) * 2 > P:
            break
        for ap in range(1, bp + 1):
            if gcd(ap, bp) != 1:
                continue
            s = ap + bp
            if s * 2 > P:
                break
            max_gs = P // s  # g + k <= max_gs

            for g in range(2, max_gs):
                k_min = (g * bp + s - 1) // s  # ceil(g*bp/s)
                k_max = min(g - 1, max_gs - g)
                if k_min > k_max:
                    continue
                count += k_max - k_min + 1

    print(count)

if __name__ == "__main__":
    solve()