题目大意
这是一道提交答案题。要求找出两个正整数 $a, b$，满足 $a, b \le 2 \times 10^{9}$，且 $c = f(a, b)$ 尽可能小。其中：
如果 $c \le 10^{-18}$，得满分。
预计难度：普及组。
部分分如下：
- 若 $c \le 10^{-3}$，得 $10$ 分。
- 若 $c \le 10^{-8}$，得 $30$ 分。
- 若 $c \le 10^{-13}$，得 $60$ 分。
- 若 $c \le 10^{-18}$，得 $100$ 分。
思路分析
算法一
不难发现题目要求就是让 $\frac{a}{b}$ 尽可能地接近 $\sqrt{2}$。
根据常识，$\sqrt{2}$ 大约等于 $1.414$，所以输出 1414 1000 即可达到 $c \le 10^{-3}$ 的准确率。
期望得分 $10$ 分。
算法二
使用计算器计算 $\sqrt{2}$ 大约等于 $1.41421356$，所以输出 141421356 100000000 即可达到 $c \le 10^{-8}$ 的准确率。
期望得分 $30$ 分。
算法三
我们枚举 $b$，计算 $\lfloor \sqrt{2} \times b \rfloor$ 以及 $\lfloor \sqrt{2} \times b \rfloor + 1$ 作为 $a$ 的备选，取最优的 $(a, b)$ 即可。
不幸的是，时间有限，我们只能枚举 $1 \le b \le 10^7$。不过这样已经可以达到 $c \le 10^{-13}$ 的准确率。
期望得分 $60$ 分。
算法四
由于这是提交答案题，我们在本地枚举 $b$ 即可。这样可以达到 $c \le 10^{-18}$ 的准确率。
期望得分 $100$ 分。
算法五
算法四太不优美了。有没有漂亮的做法呢？
计算 $(\sqrt{2} - 1) ^ k$ = $a \times \sqrt{2} + b$ 即可。发现随着 $k$ 的增大，$- \frac{a}{b}$ 越来越接近 $\sqrt{2}$。经过实践发现取 $k = 25$ 最为合适。
期望得分 $100$ 分。
代码实现
1 | |
2 | using namespace std; |
3 | |
4 | const int n = 25; |
5 | int a[n + 3], b[n + 3]; |
6 | |
7 | int main() { |
8 | a[0] = 1, b[0] = 0; |
9 | for (int i = 1; i <= n; i++) { |
10 | a[i] = 2 * b[i - 1] - a[i - 1]; |
11 | b[i] = a[i - 1] - b[i - 1]; |
12 | } |
13 | int x = a[n], y = b[n]; |
14 | if (n & 1) x = -x; |
15 | else y = -y; |
16 | printf("%d %d\n", x, y); |
17 | return 0; |
18 | } |