【codejam2008 Round1A】Numbers 题解

题目大意

  求 $(3+\sqrt 5)^n$ 的整数部分最后三位。
  $n \le 2 \times 10^9$

这真是个有趣的问题

解法

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

  但是直接这样矩阵乘法不能模！！！
  原因是，$a=a\bmod 1000$，但 $b\sqrt 5≠(b \bmod 1000)\sqrt 5$

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

  （个人感觉妙啊。。。）