Google编程竞赛题：计算 (3 + √5)^n 的整数部分末三位数

By Long Luo

袁哥在微博上发布了一道 数学挑战题 ：

计算 $(3+ \sqrt{5})^n$ 的整数末三位数，给出能口算或者可以用计算器计算的算法的第一个人，免费给一个价值 1000 元的 A9 投资分享群入群名额。

最开始看到这道题目时，我觉得很简单啊，于是给出了下面的解答：

令 $y = (3+ \sqrt{5})^n$ ，两边同取对数，$\log_{10}{y} = n \log_{10}{(3+\sqrt5)}$ ， $y = 10^{n\log_{10}{5.23607}}$ ，$lg5 \approx 0.7$ ，所以 $y \approx 10^{0.7n}$ 。

但问题没有这么简单，因为上述解答只在 $n = 1$ 是正确的，$n = 2$ , $y = 10^{1.4} = 25$ 就不对了，因为精度不够！

之外，根据评论中其他人给的思路，分析得出这个是周期性的，所以又提交了下面的答案：

但问题仍然没有这么简单，因为即使循环周期 $k = 100$ , $\log_{10}{(3+\sqrt5)}$ 取的位数再多仍然会出现精度不够的问题。

之后袁哥发布了 解答 ，图片太大，这里放 链接 。

袁哥的题解省略了很多东西，很多人可能看不太明白。我重新写了题解，重新整理了思路及缺失的步骤，外加证明，有高一数学水平即可看懂。

后来通过搜索，发现这道题是 Google CodeJam^[1] 编程竞赛题，原题如下：

Problem:
In this problem, you have to find the last three digits before the decimal point for the number $(3 + \sqrt{5})^n$ .
For example, when $n = 5$ , $(3 + \sqrt{5})^5 = 3935.73982...$ , The answer is $935$ .
For $n = 2$ , $(3 + \sqrt{5})^2 = 27.4164079...$ , The answer is $027$ .

Input:
The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n.

Output:
For each input case, you should output:

Case #X: Y
where X is the number of the test case and Y is the last three integer digits of the number (3 + √5)n. In case that number has fewer than three integer digits, add leading zeros so that your output contains exactly three digits.

Limits
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100

Small dataset (Test set 1 - Visible)
2 ≤ n ≤ 30

Large dataset (Test set 2 - Hidden)
2 ≤ n ≤ 2000000000

这道题有好几种方法可以解决！

最核心的就是利用共轭根式^[2] ，$3 - \sqrt{5}$ 就是 $3 + \sqrt{5}$ 的共轭。

设 $a = 3 + \sqrt{5}$ , $b = 3 - \sqrt{5}$ , 则 $f(n) = a^n + b^n$ .

可以构造一个数列：

$f(n) = (3 + \sqrt{5})^n + (3 - \sqrt{5})^n , n = 1, 2, \dots$

可以证明 $f(n)$ 为整数^[3] ，显然 $0 < b < 1$ , $b^n$ 构成一个等比数列， 那么 $f(n) - 1 < a^n < f(n)$ 。

参考资料

---

1. Google CodeJam ↩︎

2. 共轭 ↩︎

3. 共轭根式为整数 ↩︎