Grodno 2015 (Urozero May 2015 Day 5) D Triangles

给出$P(<=10^9)$, 求有多少个有序三元组$(a, b, c),\ gcd(a, b, c) = 1,\ a + b + c <= P$且以它们构成的三角形中存在某个角是另外一个角的两倍。
题解：
不妨设$a,b,c$所对的角分别是$A,B,C$且$C = 2*A$.
根据正弦定理
$$\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C}$$
$$\frac{a}{\sin A} = \frac{b}{\sin (\pi-3A)} = \frac{c}{\sin 2A}$$
$$\frac{a}{\sin A} = \frac{b}{\sin 3A} = \frac{c}{\sin 2A}$$
$$\frac{a}{\sin A} = \frac{b}{3 \sin A - 4\sin^3 A} = \frac{c}{2\sin A \cos A}$$
$$a = \frac{b}{3 - 4\sin^2 A} = \frac{c}{2 \cos A}$$ $$a = \frac{b}{4\cos^2 A - 1} = \frac{c}{2 \cos A}$$
可以得到$\cos A = \frac{c}{2a}$ 代入$\frac{b}{4\cos^2 A - 1}$得$a*(a+b)=c^2$
上面的推导是充要的。
易得$gcd(a, b) = 1, 否则gcd(a, b, c) \ne 1$, 所以还有$gcd(a, a + b) = 1$。
因此$a$和$a+b$都是完全平方数。不妨设$a = u^2$, $a + b = v^2$.
还要满足构成三角形的条件 :
$$a+b>c \Rightarrow v^2 > uv \ \ 显然成立$$
$$a+c>b \Rightarrow u^2+uv>v^2-u^2 \Rightarrow 2u^2+uv-v^2>0 \Rightarrow u > \frac{v}{2}$$
$$a+b+c <= P \Rightarrow v^2+uv<=P \Rightarrow u <= \frac{P-v^2}{u}$$
所以得出做法：枚举v，则有$u>\frac{v}{2}+1 , u < v , u <= \frac{P-v^2}{u}$ 且$gcd(u, v) = 1$.
根据$v$的质因子容斥一下求出所有合法的u个数即可。

巴特西

Grodno 2015 (Urozero May 2015 Day 5) D Triangles

最新文章

热门文章