Google code jam 2008 Round 1A(c.Numbers)题解

本文主要是介绍Google code jam 2008 Round 1A(c.Numbers)题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

   题目是计算（3＋sqrt(5))^n的小数点前三位数，不足三位补0,正整数n的最大值为20亿。

   http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtchALEghjb250ZXN0cxiE2QUM



   经过两天的努力，终于把这道题搞明白了，为了方便后人的学习现将算法整理下来。


令f（n）＝（3＋sqrt（5））^n;
以前做过整数的n次方求余的题，但是这题的底数为实数，因此首先设法将其化为整数，
令g（n）＝f（n）＋（3－sqrt（5））^n，可以发现g（n）为f（n）的向上取整，因为（3－sqrt（5））^n小于1，所以g（n）减1所 得结果的后三位既为本题所求。下面的问题就是如何求g（n）了，经过数学推导有以下关 系，g（n＋2）＝6g（n）－4g（n），g（0）＝2，g（1）＝6，有了这个递推关系就可以求g（n）了，但朴素算法的时间复杂度为o(n),这里 介绍一个为o（lnn&

这篇关于Google code jam 2008 Round 1A(c.Numbers)题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---