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)}\) 取的位数再多仍然会出现精度不够的问题。
袁哥的题解省略了很多东西，很多人可能看不太明白。我重新写了题解，重新整理了思路及缺失的步骤，外加证明，有高一数学水平即可看懂。
问题 :
对于任意 \(n \subset N\) , 求 \((3 + \sqrt{5})^n\) 整数部分最后 \(3\) 位。
Solution
设 \(a^n = (3 + \sqrt{5})^n , b^n = (3 - \sqrt{5})^n\) ，
\[ f(n) = a^n + b^n \]
证明 1: \(f(x)\) 为整数。 方法〈》: 根据项展开式: \(f(n)=2 \cdot \sum_{k=0}^{n / 2} C_n^{2 k} \cdot 3^{n-2 k} \cdot 5^k\langle(\rangle\)奇次项相消, 证毕!
\[ \begin{aligned} & \text { 方法 }\left\langle 27 \text { 根据 } A^{n+1}+B^{n+1}=(A+B)\left(A^n+B^n\right)-A B\left(A^{n-1}+B^{n-1}\right)\right. \\ & \text { 代入 } A=3+\sqrt{5}, B=3-\sqrt{5}, A B=9-5=4 \\ & \text { 可得: } f_{n+1}=6 f_n-4 f_{n-1}, n \geqslant 1 \quad \ldots . \text { 《2 } \\ & f_0=2, f_1=6, f_2=28, \text { 递推 } f_n C Z^{+} \text {证毕 } \\ & \text { 由 } 0<3-\sqrt{5}<1,0<b^n<1, f_n=N, \end{aligned} \]
\(\Rightarrow N-k a^n<N\) ，故题目转化为求 \(f_n\) 最后 3 位， fn \(\% 1000\) 。根据结果 ans \(=f_n \%\). 1000 , 证明ans是周期性。
证明: \(\because f_n=6 f_n-4 f_{n-1}\), 考虑以下数值对: 模运算法则: \((a * b) \% p=(a \% p * b \% p) \% p\)
\[ a^b \% p=\left((a \% p)^b\right) \% p \]
证明 1: 为整数。 方法〈》: 根据项展开式: 奇次项相消, 证毕!
方法根据代入可得《递推证毕由 ，故题目转化为求 最后 3 位， fn 。根据结果 ans . 1000 , 证明ans是周期性。 证明: , 考虑以下数值对: 模运算法则:
后来通过搜索，发现这道题是 Google CodeJam1 编程竞赛题，原题如下：
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 \]
显然 \(0 < b < 1\) , \(b^n\) 构成一个等比数列， 那么 \(f(n) - 1 < a^n < f(n)\) 。
可以证明 \(f(n)\) 为整数3。