by 小伟
Google Code Jam Round1A "Number"
题目描述:给定一个数n(2 <= n <= 2000000000),求的整数部分最后三位。
For example, when n = 5, The answer is 935.
解法:
1. 直接求,要求精度高,当n>28时,结果就出错。
2. 技巧解法,配数法:
首先设
把展开,得到:
展开后发现,包含 的项都相互抵消了,得到:
从上式中可以看出,G(X)是整数。
由于,因此。
于是问题就转化为求,求也是使用配数法,如下:
因此,得到递推公式
由于题目中的n值较大,不能直接使用递推公式,我们可以构造一个矩阵来加速求解:
其中,所以
使用按位乘法,就可以在Log(x)的复杂度内,求出G(X)。
至此,本题顺利解决。