Problem Description
You know the date type double can guarantee the precision about 15 or 16 digits.
But in this problem, you have to calculate ⌊ ( 2 + 3 ) 2 n ⌋ m o d 1024 \left\lfloor\left(\sqrt{2}+\sqrt{3}\right)^{2n}\right\rfloor\bmod 1024 ⌊ ( 2 + 3 ) 2 n ⌋ mod 1024 .
For example, when n = 2 n=2 n = 2 , ( 2 + 3 ) 4 = 97.9897 ⋯ \left(\sqrt{2}+\sqrt{3}\right)^4=97.9897\cdots ( 2 + 3 ) 4 = 97.9897 ⋯ , ⌊ ( 2 + 3 ) 4 ⌋ m o d 1024 = 97 \left\lfloor\left(\sqrt{2}+\sqrt{3}\right)^{4}\right\rfloor\bmod 1024=97 ⌊ ( 2 + 3 ) 4 ⌋ mod 1024 = 97 .
The first line of input gives the number of cases, T T T . T T T test cases follow, each on a separate line. Each test case contains one positive integer n n n . (1 ≤ n ≤ 1 0 9 1 \le n \le 10^9 1 ≤ n ≤ 1 0 9 )
Output
For each input case, you should output the answer in one line.
Sample Output
Idea
( 2 + 3 ) 2 n = ( 5 + 2 6 ) n = ∑ k = 0 n C n k ⋅ 5 k ⋅ ( 2 6 ) n − k \left(\sqrt{2}+\sqrt{3}\right)^{2n}=(5+2\sqrt 6)^n=\sum\limits_{k=0}^nC_n^k\cdot5^k\cdot (2\sqrt 6)^{n-k} ( 2 + 3 ) 2 n = ( 5 + 2 6 ) n = k = 0 ∑ n C n k ⋅ 5 k ⋅ ( 2 6 ) n − k ,将有理项和无理项分开;不妨设 ( 5 + 2 6 ) n = x n + y n 6 (5+2\sqrt 6)^n=x_n+y_n\sqrt 6 ( 5 + 2 6 ) n = x n + y n 6 ,其中 x n , y n ∈ N ∗ x_n,y_n\in\mathbb N^\ast x n , y n ∈ N ∗ ;根据二项式的性质,又有 ( 5 − 2 6 ) n = x n − y n 6 (5-2\sqrt6)^n=x_n-y_n\sqrt 6 ( 5 − 2 6 ) n = x n − y n 6 。
首先,( 5 + 2 6 ) n + ( 5 − 2 6 ) n = 2 x n (5+2\sqrt 6)^n+(5-2\sqrt6)^n=2x_n ( 5 + 2 6 ) n + ( 5 − 2 6 ) n = 2 x n ,故 ⌊ ( 5 + 2 6 ) n ⌋ = ⌊ 2 x n − ( 5 − 2 6 ) n ⌋ = 2 x n − 1 \lfloor(5+2\sqrt 6)^n\rfloor=\lfloor2x_n-(5-2\sqrt6)^n\rfloor=2x_n-1 ⌊( 5 + 2 6 ) n ⌋ = ⌊ 2 x n − ( 5 − 2 6 ) n ⌋ = 2 x n − 1 。
显然有递推式
$$
\begin{aligned}&(5+2\sqrt 6)^n\\=&(5+2\sqrt 6)^{n-1}\cdot (5+2\sqrt 6)\\=&(x_{n-1}+y_{n-1}\sqrt 6)\cdot(5+2\sqrt 6)\\=&5x_{n-1}+2\sqrt 6x_{n-1}+5\sqrt 6y_{n-1}+12y_{n-1}\\=&(5x_{n-1}+12y_{n-1})+(2x_{n-1}+5y_{n-1})\sqrt 6\end{aligned}
$$
又有定义 ( 5 + 2 6 ) n = x n + y n 6 (5+2\sqrt 6)^n=x_n+y_n\sqrt 6 ( 5 + 2 6 ) n = x n + y n 6 ,故得到
x n = 5 x n − 1 + 12 y n − 1 y n = 2 x n − 1 + 5 y n − 1 x_n=5x_{n-1}+12y_{n-1}\\ y_n=2x_{n-1}+5y_{n-1}
x n = 5 x n − 1 + 12 y n − 1 y n = 2 x n − 1 + 5 y n − 1
可构造矩阵递推式
$$
\begin{pmatrix}5&12\\2&5\end{pmatrix}\begin{pmatrix}x_{n-1}\\y_{n-1}\end{pmatrix}=\begin{pmatrix}x_n\\y_n\end{pmatrix}
$$
即
$$
\begin{pmatrix}5&12\\2&5\end{pmatrix}^{n-1}\begin{pmatrix}x_1\\y_1\end{pmatrix}=\begin{pmatrix}x_n\\y_n\end{pmatrix}
$$
全程在 m o d 1024 \bmod 1024 mod 1024 的意义下计算,不存在浮点误差和数值溢出的问题;答案为 ( 2 x n − 1 ) m o d 1024 (2x_n-1)\bmod 1024 ( 2 x n − 1 ) mod 1024 ,时间复杂度为 O ( log n ) O(\log n) O ( log n ) 。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 #include <iostream> #include <cstring> using namespace std;typedef long long ll;const int MOD=1024 ;struct Matrix { ll m[3 ][3 ]; Matrix (){ memset (m,0 ,sizeof (m)); } }; Matrix operator *(const Matrix& x,const Matrix& y){ Matrix res; for (int i=1 ;i<=2 ;i++){ for (int j=1 ;j<=2 ;j++){ for (int k=1 ;k<=2 ;k++){ res.m[i][j]+=x.m[i][k]*y.m[k][j]; res.m[i][j]%=MOD; } } } return res; } Matrix quickMatrixPow (Matrix a,ll b) { Matrix res; res.m[1 ][1 ]=res.m[2 ][2 ]=1 ; while (b){ if (b&1 ){ res=res*a; } a=a*a; b>>=1 ; } return res; } int main () { ios::sync_with_stdio (false ); int _; for (cin>>_;_;_--){ int n; cin>>n; Matrix A; A.m[1 ][1 ]=A.m[2 ][2 ]=5 ; A.m[1 ][2 ]=12 ; A.m[2 ][1 ]=2 ; A=quickMatrixPow (A,n-1 ); ll a=1ll *(5 *A.m[1 ][1 ]+2 *A.m[1 ][2 ])%MOD; cout<<(2 *a-1 +MOD)%MOD<<endl; } return 0 ; }