当前位置 博文首页 > Keven_11的博客:C++题解:Pell数列
??????目录
题目?
题解
Pell?数列 a1?,a2?,a3?,...?的定义是这样的,a1?=1,a2?=2,...,an?=2×an?1?+an?2?(n>2)。
小蒜给出一个正整数?k,要求Pell?数列的第?k?项模上?32767?是多少。
输入格式
第?11?行是测试数据的组数 n(1≤n≤20),后面跟着?n?行输入。每组测试数据占?1?行,包括一个正整数 k(1≤k<1000000)。
输出格式
n?行,每行输出对应一个输入。输出应是一个非负整数。
输出时每行末尾的多余空格,不影响答案正确性
要求使用「文件输入输出」的方式解题,输入文件为?
pell.in
,输出文件为?pell.out
样例输入
2 1 8样例输出
1 408题解:
知识点:递推
分析:?无他,但死干也
代码:
cs#include<iostream> #include<cstdio> #define _for(i,a,b) for (int i=(a);i<=(b);i++) using namespace std; const int MOD=32767,N=1e6+5;//注意取模 int dp[N]; int main(){ freopen("pell.in","r",stdin); freopen("pell.out","w",stdout); dp[1]=1; dp[2]=2; _for(i,3,N){ dp[i]=(2*dp[i-1]%MOD+dp[i-2]%MOD)%MOD;//注意多次取模 } int n; scanf("%d",&n); while (n--){ int k; scanf("%d",&k); printf("%d\n",dp[k]); } return 0; }
下一篇:没有了