By Long Luo

$$y = (3+ \sqrt{5})^n$$ ，两边同取对数，$$\log_{10}{y} = n \log_{10}{(3+\sqrt5)}$$$$y = 10^{n\log_{10}{5.23607}}$$$$lg5 \approx 0.7$$ ，所以 $$y \approx 10^{0.7n}$$

# Solution

$$a^n = (3 + \sqrt{5})^n , b^n = (3 - \sqrt{5})^n$$

$f(n) = a^n + b^n$

\begin{aligned} & \text { 方法 }\left\langle 27 \text { 根据 } A^{n+1}+B^{n+1}=(A+B)\left(A^n+B^n\right)-A B\left(A^{n-1}+B^{n-1}\right)\right. \\ & \text { 代入 } A=3+\sqrt{5}, B=3-\sqrt{5}, A B=9-5=4 \\ & \text { 可得: } f_{n+1}=6 f_n-4 f_{n-1}, n \geqslant 1 \quad \ldots . \text { 《2 } \\ & f_0=2, f_1=6, f_2=28, \text { 递推 } f_n C Z^{+} \text {证毕 } \\ & \text { 由 } 0<3-\sqrt{5}<1,0<b^n<1, f_n=N, \end{aligned}

$$\Rightarrow N-k a^n<N$$ ，故题目转化为求 $$f_n$$ 最后 3 位， fn $$\% 1000$$ 。根据结果 ans $$=f_n \%$$. 1000 , 证明ans是周期性。

$a^b \% p=\left((a \% p)^b\right) \% p$

Problem: In this problem, you have to find the last three digits before the decimal point for the number $$(3 + \sqrt{5})^n$$ . For example, when $$n = 5$$ , $$(3 + \sqrt{5})^5 = 3935.73982...$$ , The answer is $$935$$ . For $$n = 2$$ , $$(3 + \sqrt{5})^2 = 27.4164079...$$ , The answer is $$027$$ .

Input: The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n.

Output: For each input case, you should output:

Case #X: Y where X is the number of the test case and Y is the last three integer digits of the number (3 + √5)n. In case that number has fewer than three integer digits, add leading zeros so that your output contains exactly three digits.

Limits Time limit: 30 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100

Small dataset (Test set 1 - Visible) 2 ≤ n ≤ 30

Large dataset (Test set 2 - Hidden) 2 ≤ n ≤ 2000000000

$$a = 3 + \sqrt{5}$$ , $$b = 3 - \sqrt{5}$$ , 则 $$f(n) = a^n + b^n$$ .

$f(n) = (3 + \sqrt{5})^n + (3 - \sqrt{5})^n$