P13459 Numbers 题解

1. 题意解释

求出 $(3+\sqrt5)^n$ 的整数部分的后三位。

2. 思路

显然不可以 double 直接暴力算，精度会炸。

高精度吗？出门右转高精度开根，看看什么难度。

我们考虑拆开括号，容易发现 $(3+\sqrt5)^n=A_n+B_n\sqrt5$，其中 $A_n,B_n$ 都为整数。

同理有 $(3-\sqrt5)^n=A_n-B_n\sqrt5$。

故我们有 $(3+\sqrt5)^n+(3-\sqrt5)^n=2A_n$。

移项，有 $(3+\sqrt5)^n=2A_n-(3-\sqrt5)^n$。

而我们知道 $2^2=4<5<9=3^2$，故有 $2<\sqrt5<3$。

故有 $0<3-\sqrt5<1$。

因此 $0<(3-\sqrt5)^n<1$。

所以我们知道 $(3+\sqrt5)^n$ 的整数部分即为 $2A_n-1$。

考虑如何求出 $A_n$。

我们不难发现 $(3+\sqrt5)(A_i+B_i\sqrt5)=A_{i+1}+B_{i+1}\sqrt5$。

拆开括号即得 $3A_i+5B_i=A_{i+1},A_i+3B_i=B_{i+1}$。

不难想到矩阵加速。

我们构造矩阵 $\begin{bmatrix}3&5\1&3\end{bmatrix}$，不难发现 $\begin{bmatrix}A_i\B_i\end{bmatrix}\times\begin{bmatrix}3&5\1&3\end{bmatrix}=\begin{bmatrix}3A_i+5B_i\A_i+3B_i\end{bmatrix}=\begin{bmatrix}A_{i+1}\B_{i+1}\end{bmatrix}$。

而我们又有 $A_0=1,B_0=0$。

故而有 $\begin{bmatrix}1\0\end{bmatrix}\times\begin{bmatrix}3&5\1&3\end{bmatrix}^n=\begin{bmatrix}A_n\B_n\end{bmatrix}$。

至此这道题就做完了，记得注意输出格式。

3. 代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000;
int n,t,tot=1;
struct matrix{
	int a[5][5];
};
matrix operator*(matrix A,matrix B){
	matrix C;
	for(int i=1;i<=2;i++){
		for(int j=1;j<=2;j++){
			int cnt=0;
			for(int k=1;k<=2;k++){
				cnt=(cnt+A.a[i][k]*B.a[k][j])%mod;
			}
			C.a[i][j]=cnt;
		}
	}
	return C;
}//矩乘
matrix qpow(matrix base,int up){
	matrix ret;
	memset(ret.a,0,sizeof ret.a);
	for(int i=1;i<=2;i++){
		ret.a[i][i]=1;
	}
	while(up){
		if(up&1){
			ret=ret*base;
		}
		base=base*base;
		up>>=1;
	}
	return ret;
}//矩阵快速幂
signed main(){
	cin>>t;
	while(t--){
		cin>>n;
		cout<<"Case #"<<tot<<": ";
		tot++;
		matrix A;
		A.a[1][1]=3,A.a[1][2]=5,A.a[2][1]=1,A.a[2][2]=3;//转移矩阵
		matrix tmp=qpow(A,n);
		int ans=(tmp.a[1][1]*2-1)%mod;//最后乘上初始矩阵算答案
		if(ans>=100&&ans<=999){
			cout<<ans<<endl;
		}
		else if(ans>=10&&ans<=99){
			cout<<"0"<<ans<<endl;
		}
		else{
			cout<<"00"<<ans<<endl;
		}
	}
	return 0;
}