这道题直接用斐波那契递推公式求解即可。（f[i]=f[i-1]+f[i-2]）

递推部分代码：

const int N=1e6;
long long t,f[N+100];
void fib(){
	f[1]=f[2]=1;
	For(i,3,N) f[i]=f[i-1]+f[i-2];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>t;
	fib();
	while(t--){
		long long k;
		cin>>k;
		cout<<f[k]<<'\n';
	}

千万别用递归，会超时 记得开long long~

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000001;
long long a[MAXN+100],n,m[MAXN+100],x=-100;
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	ios::sync_with_stdio;
	cin.tie(0);
	cout.tie(0);//输入输出优化
	a[1]=1;
	a[2]=1;

	for(int i=1;i<=n;i++){
		cin>>m[i];
		x=max(m[i],x);//求最大值
	}
	for(int i=3;i<=x;i++){
		a[i]=a[i-1]+a[i-2];//建立斐波那契数列
	}
	for(int i=1;i<=n;i++)cout<<a[m[i]]<<endl;//输出
	return 0;
}