学步园

Numbers，这道题是Round 1A 2008的最后一道题，给定n，要求计算(3 + √5)^n整数部分的最后三位数字，如n = 5, (3 + √5)⁵ = 3935.73982，那么结果就应该是935，不足三位数字，则补零。

(3 + √5)ⁿ⁺¹与(3 + √5)ⁿ有递推关系，用a_n+b_n√5表示(3 + √5)ⁿ，那么 α^{(n + 1)} = (3 + √5)(a_n + b_n√5) = (3a_n + 5b_n) + (3b_n + a_n)√5，可以写成矩阵形式，

在contest analysis里面也给出了Python的解题代码，如下，

#!/usr/bin/python
#encoding:UTF-8
#Filename:Numbers.py

import sys

def matrix_mult(A, B):
    C = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
for k in range(2):
                C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % 1000
return C

def fast_exponentiation(A, n):
if n == 1:
return A
else:
if n % 2 == 0:
            A1 = fast_exponentiation(A, n/2)
return matrix_mult(A1, A1)
else:
return matrix_mult(A, fast_exponentiation(A, n - 1))

def solveF(n):
    A = [[3, 5], [1, 3]]
    A_n = fast_exponentiation(A, n)
return (2 * A_n[0][0] + 999) % 1000
#    return int(A_n[0][0]+A_n[1][0]*s5)%1000

inname = "input.txt"
outname = "output.txt"
if len(sys.argv)>1:
    inname = sys.argv[1]
    outname = inname.rstrip(".in")
    outname = outname + ".out"
fin = open(inname,"r")
fout = open(outname,"w")

caseNum = 0

line = fin.readline()
testCaseNum = int(line)
lines = fin.readlines(testCaseNum)
for line in lines:
    caseNum = caseNum + 1
    line = line.rstrip("\n")
    n = int(line)

    s5 = 2.236067977

    b = solveF(n)

    answer = "Case #%d: " %(caseNum)
if b<100:
        answer = answer + "0" + str(b)
else:
        answer = answer + str(b)
    answer = answer + "\n"

    fout.write(answer)

fin.close()
fout.close()

测试结果是，对于small case测试可以通过，对于large case结果显示不正确。
代码中还有一个地方觉得比较奇怪，在solveF返回值的地方，不是应该计算a_n+b_n√5吗？为什么连√5都没有出现呢？