大斐波那契数取余
From Admin☆ 描述 Description 著名的斐波那契数列
f[n]=1 n=1,2
f[n-1]+f[n-2] n>2
现在求第n项，由于f[n]可能很大，你只需要输出mod 32768的值即可。 输入格式 Input Format 仅有一行，为n,1<=n<=maxlongint 输出格式 Output Format 仅有一个数字，即答案 样例输入 Sample Input [复制数据]
样例输出 Sample Output [复制数据]
/*由于题目是对32768求余，即2的15次方，可以找出循环节规律，当对2求余时，循环节长度为3，对4求余时，循环节长度为3*2，对8求余时，循环节长度为3*(2的平方)即3*(2^2),对16求余时，循环节长度为3*(2^3)......即对2^n求余，循环节长度为3*(2^(n-1)).所以对于32768求余，循环节长度为32768/2*3=49152,然后就不用多说了吧~~*/#include <iostream>using namespace std;int a[50005];int main(){long long n,i;a[1]=a[2]=1;for(i=3;i<=50000;i++){ a[i]=a[i-1]+a[i-2]; if(a[i]>=32768) a[i]%=32768;}cin>>n;cout<<a[n%49152]<<endl;return 0;}