C++ 求Pell数列

Pell数列是这样定义的：a1=1,a2=2,...,an=2an-1+an-2
现在求出Pell数列的第k项模上32767的余数是多少。

第一行为正整数T，表示存在T组测试数据。
每组测试数据输入一行包含一个正整数k(1<=k<=1000000)。

对于每组测试数据输出一行表示答案。

有两种方式，第一种比较耗时

#include <iostream>
using namespace std;
int aaa(int a)
{
	if (a <= 2)
	{
		return a;
	}
	else
	{
		return (2 * aaa(a - 1) + aaa(a - 2)) % 32767;
	}
}
int main()
{
	int t;
	cin >> t;
	int a;
	for (int i = 1; i <= t; i++)
	{
		cin >> a;
		cout << aaa(a) << endl;
	}
}

第二种就是提前建立一个大的数组，提前把pell数列的数存在这个数组之中，相对来说比较耗内存

#include <iostream>
using namespace std;
#define N 1000001    
int arr[N];       //提前定义好数组
void aaa(int n)
{
	arr[0] = 0;
	arr[1] = 1;
	arr[2] = 2;
	for (int i = 3; i <= n; i++)
	{
		arr[i] = (2 * arr[i - 1] + arr[i - 2]) % 32767;   //提前将pell数列余32767的结果存 
                                                          //在数组中，到时候直接输出数组内
	}                                                     // 的数
}
int main()
{
	int t;
	int a;
	cin >> t;
	aaa(N);                                
	for (int i = 1; i <= t; i++)
	{
		cin >> a;
		cout << arr[a] << endl;
	}

}