Project Euler 296

题目

Angular Bisector and Tangent

Given is an integer sided triangle \(ABC\) with \(BC \le AC \le AB\).

\(k\) is the angular bisector of angle \(ACB\). \(m\) is the tangent at \(C\) to the circumscribed circle of \(ABC\). \(n\) is a line parallel to \(m\) through \(B\).

The intersection of \(n\) and \(k\) is called \(E\).

How many triangles \(ABC\) with a perimeter not exceeding \(100 000\) exist such that \(BE\) has integral length?

解决方案

令\(D=k\cap AB,|BC|=a,|AC|=b,|AB|=c,\odot P\)为\(\triangle ABC\)的外接圆。且\(n\cap\odot P=\{B,G\}\)。

令\(\angle ACD=\angle BCD=\alpha,CB\)和切线\(m\)的夹角为\(\beta\)。

那么因为\(m\parallel n\)，所以\(\angle CBE=\beta\)。

那么有\(\angle DEB=\angle BCD+\angle CBE=\alpha+\beta\).

可以知道，由于\(m\)是\(\odot P\)的切线，因此\(CP\bot n\)，从而有\(\widehat{CG}=\widehat{CB}\)，因此有\(\angle CAB=\angle CBE=\beta\)。

那么有\(\angle CDB=\angle CAB+\angle ACD=\beta+\alpha=\angle DEB\)，因此\(\triangle DEB\)是等腰三角形，所以有\(|BE|=|BD|\)。

根据角平分线定理，可以得到\(|BD|=\dfrac{ac}{a+b}\)。

为了保证\(\dfrac{ac}{a+b}\)这个值是整数，我们考虑枚举每对互质的\(a,b\)，然后计算\(c\)的数量。为了节省计算最大公因数的过程，我们考虑使用Stern-Brocot Tree来枚举每一对互质的\((a,b)\)。由于\(a,b\)互质，因此\(a,a+b\)一定也互质。那么，枚举的\(c\)一定是\(a+b\)的倍数。我们枚举好每对互质的\(a,b\)后，再枚举\(g\)使得\(a'=ga,b'=gb\)，这时的三角形第三条边\(c'\)必定满足如下条件：

\(\begin{aligned} &c'\le N-(a+b)g\\ &c'<(a+b)g\\ &c'\ge bg\\ &a+b\mid c' \end{aligned}\)

由此可以计算出，满足上面\((a,b,g)\)条件的\(c\)一共有\(\left\lfloor\dfrac{\min((a+b)g-1,N-(a+b)g)}{a+b}\right\rfloor-\left\lfloor\dfrac{bg}{a+b}\right\rfloor\)个。由此枚举相加即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000;
ll ans=0;
void dfs(int lu,int ld,int ru,int rd){
    int a=lu+ru,b=ld+rd;
    if(a+4*b>N) return;
    int d=a+b;
    for(int g=1;;g++){
        int c_min=g*b,c_max=min(d*g-1,N-d*g);
        if(c_min>c_max) break;
        ans+=c_max/d-(c_min-1)/d;
    }
    dfs(lu,ld,a,b);
    dfs(a,b,ru,rd);
}
int main(){
    for(int g=1;;g++){
        int c_min=g,c_max=min(2*g-1,N-g*2);
        if(c_min>c_max) break;
        ans+=c_max/2-(c_min-1)/2;
    }
    dfs(0,1,1,1);
    printf("%lld\n",ans);
}