Algorithm‧ICPC‧Programming: Google Code Jam Round 1A Numbers

This problem simply asks about the three digits before decimal points for $(3+\sqrt{5})^N$ .
$N$ can be very large.

The idea is very simple. Since the required number is in surd form, its $N^{\mbox{th}}$ power is also in surd form, namely $(3+\sqrt{5})^N = a+b\sqrt{3}\mbox{, where} a, b \in \mathbb{Z}$ . Consider it's conjucate $(3-\sqrt{5})^N$ , it is not difficult to verify that it's $N^{\mbox{th}}$ power is also in surd form, namely $(3-\sqrt{5})^N = a-b\sqrt{3}$ . Note that $(3+\sqrt{5})^N + (3-\sqrt{5})^N = 2a$ and since $3-\sqrt{5} < 1$ , that means the sum should be nearly $(3+\sqrt{5})^N$ itself. The final answer is just to consider the round off by 1, and giving the answer by considering $2a-1$ is enough.

Remember $a$ can be calculated by:
$a = \sum_{i=0}^{\lfloor\frac{N}{2}\rfloor}(\mbox{C}^{N}_{2i}3^{(N-2i)}5^i)$

Algorithm‧ICPC‧Programming

2008年7月30日星期三

Google Code Jam Round 1A Numbers

沒有留言:

網誌存檔

關於我自己