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

By Long Luo

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

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

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

y=(3+5)ny = (3+ \sqrt{5})^n ,两边同取对数,log10y=nlog10(3+5)\log_{10}{y} = n \log_{10}{(3+\sqrt5)}y=10nlog105.23607y = 10^{n\log_{10}{5.23607}}lg50.7lg5 \approx 0.7 ,所以 y100.7ny \approx 10^{0.7n}

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

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

Google_CodeJam_log_solution

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

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

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

Google_CodeJam_By_Hand_solution_1

Google_CodeJam_By_Hand_solution_2

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

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

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]353 - \sqrt{5} 就是 3+53 + \sqrt{5} 的共轭。:

a=3+5a = 3 + \sqrt{5} , b=35b = 3 - \sqrt{5} , 则 f(n)=an+bnf(n) = a^n + b^n .

我们构造一个序列:

f(n)=(3+5)n+(35)nf(n) = (3 + \sqrt{5})^n + (3 - \sqrt{5})^n

显然 0<b<10 < b < 1 , bnb^n 构成一个等比数列, 那么 f(n)1<an<f(n)f(n) - 1 < a^n < f(n)

可以证明 f(n)f(n) 为整数[3]

参考资料


  1. Google CodeJam ↩︎

  2. 共轭 ↩︎

  3. 共轭根式为整数 ↩︎