【codejam2008 Round1A】Numbers 题解

题目大意

      $~~~~~~$求 (3+5√)n$(3+/sqrt 5)^n$ 的整数部分最后三位。       $~~~~~~$n<=2e9

这真是个有趣的问题

解法

      $~~~~~~$考虑一项一项地乘       $~~~~~~$某个数 a+b5√$a+b/sqrt 5$，给它乘个 3+5√$3+/sqrt 5$ 之后，会变成 (3a+5b)+(a+3b)5√$(3a+5b)+(a+3b)/sqrt 5$。       $~~~~~~$于是可以考虑矩阵乘法。

      $~~~~~~$但是直接这样矩阵乘法不能模！！！       $~~~~~~$原因是，a=a mod 1000$a=a~mod~1000$，但 b5√≠(b mod 1000)5√$b/sqrt 5≠(b~mod~1000)/sqrt 5$

      $~~~~~~$所以再考虑 (3−5√)n$(3-/sqrt 5)^n$。设 (3+5√)n=a+b5√$(3+/sqrt 5)^n=a+b/sqrt 5$，那么 (3−5√)n$(3-/sqrt 5)^n$ 就等于 a−b5√$a-b/sqrt 5$。两式相加得 2a$2a$。       $~~~~~~$又由于 0<3−5√<1$0<3-/sqrt 5<1$，所以 0<(3−5√)n<1$0<(3-/sqrt 5)^n<1$，因此答案就是 2a−1$2a-1$。       $~~~~~~$于是我们矩阵乘法只需要求 a$a$，这样就可以模了！！

      $~~~~~~$（个人感觉妙啊。。。）