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);
}