2020.07.31 yukicoder contest 259

2020.08.02 AtCoder Beginner Contest 174

Prufer 序列

生成函数

比赛名称

比赛名称

yukicoder contest 259 E - 面積Nの三角形

• 题意：给定 $n \leq 10^6$，求有多少个边长是整数且均大于 $1$ 的三角形面积为 $n$。
• 题解：考虑海伦公式 $S = \sqrt {p (p-a)(p-b)(p-c)}$，其中 $p = \dfrac {a + b + c}2$。做代换 $\begin{cases} x = p-a \\ y = p-b \\ z = p-c \\ p = x + y + z \\ \end{cases}$，有 $S^2 = xyz(x + y + z)$，且显然 $(x, y, z)$ 与 $(a, b, c)$ 一一对应。注意到 $n$ 的因数是 $O(n^{1/3})$ 级别的，因此可以暴力枚举 $x, y \mid n^2$，解一个二次方程可以得到 $z$，验证结果是否满足三角形三边关系即可。
• 备注：通过换元得到一个较好的关系式，进而解决问题。如果一开始就考虑用三角函数去表示面积的话，后面基本就没法做了。这个代换法称为 Ravi 变换，更多应用 见此。

题目名称

• 题意：
• 题解：
• 备注：

题目名称

• 题意：
• 题解：
• 备注：