Project Euler 257
Project Euler 257
题目
Angular Bisectors
Given is an integer sided triangle \(ABC\) with sides \(a \le b \le c.\) \((AB = c, BC = a\) and \(AC = b)\).
The angular bisectors of the triangle intersect the sides at points \(E, F\) and \(G\) (see picture below).
The segments \(EF, EG\) and \(FG\) partition the triangle \(ABC\) into four smaller triangles: \(AEG, BFE, CGF\) and \(EFG\).
It can be proven that for each of these four triangles the ratio \(\text{area}(ABC)/\text{area(subtriangle)}\) is rational.
However, there exist triangles for which some or all of these ratios are integral.
How many triangles \(ABC\) with perimeter \(\le100,000,000\) exist so that the ratio \(\text{area}(ABC)/\text{area}(AEG)\) is integral?
引理
角平分线定理讲述了角平分线将一个三角形划分成两部分后，各边的关系。如图，假设\(XW\)是\(\triangle XYZ\)的一条角平分线，那么满足：\(\dfrac{|XY|}{|XZ|}=\dfrac{|WY|}{|WZ|}\)。
证明：根据三角形面积公式，可以得到
\(\begin{aligned} S_{\triangle XYW}=\dfrac{1}{2}\cdot |XY|\cdot |XW|\cdot \sin \angle YXW\\ S_{\triangle XZW}=\dfrac{1}{2}\cdot |XZ|\cdot |XW|\cdot \sin \angle ZXW \end{aligned}\)
由于\(XW\)是\(\angle YXZ\)的角平分线，因此\(\sin \angle YXW=\sin \angle ZXW\)。
因此不难得到\(\dfrac{S_{\triangle XYW}}{S_{\triangle XZW}}=\dfrac{|XY|}{|XZ|}\)。
由于\(\triangle XYW,\triangle XZW\)等高，并且底相同，因此\(\dfrac{S_{\triangle XYW}}{S_{\triangle XZW}}=\dfrac{|WY|}{|WZ|}\)
最终得到\(\dfrac{|XY|}{|XZ|}=\dfrac{|WY|}{|WZ|}\)。
解决方案
令\(N=10^8\)。 不难发现，\(S_{\triangle ABC}\)和\(S_{\triangle AEG}\)可以有如下产生方式：\(S_{\triangle ABC}=\dfrac{|AC|}{|AG|}\cdot S_{\triangle AGB}=\dfrac{|AC|}{|AG|}\cdot \dfrac{|AB|}{|AE|}\cdot S_{\triangle AEG}\)
以\(\dfrac{|AC|}{|AG|}\)为例。根据引理，有\(\dfrac{|AB|}{|CB|}=\dfrac{|AG|}{|CG|}\)。根据这个比例，可以得到\(\dfrac{|AB|+|CB|}{|CB|}=\dfrac{|AG|+|CG|}{|CG|}\)。其中\(|AG|+|CG|=|AC|\)。
因此最终得到\(\dfrac{c+a}{c}=\dfrac{|AC|}{|CG|}\)。同理，得到\(\dfrac{b+a}{b}=\dfrac{|AB|}{|AE|}\)。
那么最终有
\[\dfrac{S_{\triangle ABC}}{S_{\triangle AEG}}=\dfrac{(a+b)(a+c)}{bc}\]
那么最终问题就转化成：有多少个题目中要求的\(a,b,c\)，使得式子\(k=\dfrac{(a+b)(a+c)}{bc}=\left(1+\dfrac{a}{b}\right)\left(1+\dfrac{a}{c}\right)\)的值为整数。由于\(a\le b\le c\)，因此\(k\in\{2,3,4\}\)。
接下来讨论\(k=4,3,2\)这\(3\)种情况。
当\(k=4\)时，不难发现当且仅当\(a=b=c\)时才满足。这类答案一共有\(\left\lfloor\dfrac{N}{3}\right\rfloor\)个。
从
\[(a+b)(a+c)=kbc\]
出发，做对称替换：
\[b=e-d, c=e+d (e>d\ge 0),\]
于是
\[bc=(e-d)(e+d)=e^2-d^2. \]
再令
\[f=a+e(\Rightarrow a=f-e).\]
则
\[(a+b)(a+c)=(f-e+e-d)(f-e+e+d)=(f-d)(f+d)=f^2-d^2.\]
代回方程：
\[f^2-d^2=k(e^2-d^2)\Longrightarrow f^2+(k-1)d^2=ke^2.\]
于是两种情况变成：
- \(k=2:f^2+d^2=2e^2\)
- \(k=3:f^2+2d^2=3e^2\)
并且三角形边长由\(a=f-e, b=e-d, c=e+d\)给出。
接下来分别参数化这两类方程的所有整数解，并把它们对应成三角形，再做周长计数。
\(k=2\)
从
\[f^2+d^2=2e^2\]
出发，写成：
\[(f+d)^2+(f-d)^2=4e^2.\]
令\(f+d=2u, f-d=2v\)，得\(u^2+v^2=e^2\)，这就是标准勾股方程。
因此取原始勾股参数：\(u=m^2-n^2,v=2mn,e=m^2+n^2\)，其中 \(m>n,\gcd(m,n)=1\)，且 \(m,n\) 一奇一偶。
再还原\(f=u+v=m^2+2mn-n^2,d=u-v=m^2-2mn-n^2.\)
代回三边并整体约去公因子 \(2\)（这一步不影响 \(k\)，因为比例与缩放无关），可得到一组非常简洁的三边形式（无序）：
\[(a,b,c)=\left(n(m-n),n(m+n),m(m-n)\right).\]
对这三数做三角形不等式，即联立：
\[ \left \{\begin{aligned} &n(m-n)+n(m+n)>m(m-n) \\ &n(m-n)+m(m-n)>n(m+n) \\ \end{aligned}\right. \]
可推出：\(2n<m<3n.\)
根据上述内容，可得：
\[p_2=a+b+c=n(m-n)+n(m+n)+m(m-n)=m^2+mn=m(m+n).\]
因此每一个满足条件的 \((m,n)\) 生成一个 \(k=2\) 的原始周长 \(p_2=m(m+n)\)，它的所有倍数周长 \(t·p_2\) 都是合法三角形。
\(k=3\)
方程
\[f^2+2d^2=3e^2\]
可以看成环 \(\mathbb Z[\sqrt{-2}]\) 的范数：
\[N(x+y\sqrt{-2})=x^2+2y^2.\]
注意
\[N(1-\sqrt{-2})=1^2+2\cdot 1^2=3.\]
于是令
\[f+d\sqrt{-2}=(1-\sqrt{-2})(m+n\sqrt{-2})^2\tag{1}\]
即可保证
\[N(f+d\sqrt{-2})=N(1-\sqrt{-2})\cdot N(m+n\sqrt{-2})^2=3(m^2+2n^2)^2=3e^2\]
从而满足方程（取 \(e=m^2+2n^2\)）。
展开方程\((1)\)右侧，得到：
\[e=m^2+2n^2,f=m^2+4mn-2n^2,d=-m^2+2mn+2n^2.\]
代回三角形边长\(a=f-e, b=e-d, c=e+d\)
并整体约去公因子 \(2\)（同样不影响比值），可得（无序）：
\[(a,b,c)=\left(2n(m-n),m(m-n),n(m+2n)\right).\]
类似的对上述三边做三角形不等式，可推出\(2n<m<4n\).
因此可以得到三边之和：\(p=m^2+2mn=m(m+2n).\)
但这组构造出的三边有时会有额外的公因子 \(2\)。不过可以证明在 \(\gcd(m,n)=1\) 且 \(m\not\equiv n\pmod 3\) 的前提下，公因子只可能来自 \(m\) 的奇偶：
- 若 \(m\) 为奇数，则该三角形已是原始，周长 \(p_3=p\)；
- 若 \(m\) 为偶数（此时 \(n\) 必为奇数），三边全为偶数，可再整体除以 2 得到原始三角形，周长\(p_3=\dfrac{p}{2}=\dfrac{m(m+2n)}{2}.\)
另外，若 \(m\equiv n\pmod 3\) 会产生整体公因子 \(3\)，因此我们在生成原始三角形时直接排除：\(m\not\equiv n\pmod 3\)。
最终，枚举 3 部分计数之和即为答案。
代码
1 | from tools import * |