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

By Long Luo

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

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

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

\(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\) 就不对了,因为精度不够!

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

Google_CodeJam_log_solution

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

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

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

Google_CodeJam_By_Hand_solution_1
Google_CodeJam_By_Hand_solution_2

后来通过搜索,发现这道题是 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

参考资料


  1. Google CodeJam↩︎

  2. 共轭↩︎

  3. 共轭根式为整数↩︎