Pell数列(递归）

题目描述:

Pell数列a1,a2,a3,... 的定义是这样的，a1=1, a2=2 , ... , an=2an−1+an−2 (n>2)。

给出一个正整数 k，要求Pell数列的第 k 项模上32767 是多少。

输入格式:

一个正整数k(1≤k<1000000)。

输出格式:

一个非负整数。

样例输入:

8

样例输出:

408

时间限制: 1000ms
空间限制: 256MB

代码如下：

#include<cstdio>
long long a[1000001]={};
int n,i,j;
int di(int m){
	a[m]=(2*a[m-1]+a[m-2])%32767;
	if(m==n){
		printf("%d",a[n]);
		return 0;
	}
	m++;
	di(m);
}
int main(){
	scanf("%d",&n);
	if(n==1||n==2){
		printf("%d",n);
		return 0;
	}
	a[1]=1;
	a[2]=2;
	di(3);
}