Posted on 

Pell数列与同余性质

题目

描述

Pell数列a1, a2, a3, …的定义是这样的,a1 = 1, a2 = 2, … , an = 2 * an − 1 + an - 2 (n > 2)。
给出一个正整数k,要求Pell数列的第k项模上32767是多少。

输入

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数k (1 ≤ k < 1000000)。

输出

n行,每行输出对应一个输入。输出应是一个非负整数。

思考

乍一看这是很平常的一道题,可能涉及到的知识点包括for语句和数组。但事实证明,我过于天真了。

大致结构

一开始成形的代码是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int main()
{
int n,x;
scanf("%d", &n);
// 必须定义数组的元素数目,才能确定占用的内存地址
// 其中 pell数组存放在每次遍历计算过程中数列的每一项的值,并将最后一项的值写入result数组中
int pell[10000];
int result[10000];
for (int i=1; i<=n; ++i)
{
scanf("%d", &x);
pell[1]=1;
pell[2]=2;
for (int j=3; j<=x; ++j)
{
pell[j]=pell[j-1]*2+pell[j-2];
}
result[i]=pell[x];
}
for (int i=1; i<=n; ++i)
{
printf("%d\n", result[i]);
}
return 0;
}

代入测试数据也很顺利,自然就交上去跑了,结果没过。

无奈,下载错误点输入,定睛一看,才发觉事情不对劲:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
20
1
2
767
434
10
999999
34
54563
2324
4345
9085
4334
1985
86545
9068
78954
809846
18965
6563
90568

修正答案

数组溢出

首先自然是 pell数组, 改成pell[1000000].

计算过程溢出

这里是重头戏,困扰了我很久。

首先,int数据类型最大值为32767,超过这个值就会溢出,从而使计算结果出错。那么,该如何解决呢?苦思冥想良久也没出结果的我决定打开万能的Google,用Google搜到了一篇简书(?)的文章,里面做了这样的处理:

1
2
3
4
...
pell[j]=pell[j-1]*2+pell[j-2];
pell[j] %= 32767;
...

模32767不难理解:当值小于32767值不变,当值大于32767值变小。

但是问题来了,为什么可以直接对pell[j] 进行模运算?难道不会影响后面的计算结果吗?

数学原理

同余性质

这里参考知乎:斐波那契数列取余是否有规律?

这个结论其实可以推广为,任意一个齐次线性的整数递推数列都是模周期的

以及同余的性质:

1
(a + b) mod m = (a mod m + b mod m) mod m

那么类似的:

1
(2*a + b) mod m = (2*a mod m + b mod m) mod m

得出:

将pell数列每一项求出最终取余数 = 将pell数列每一项取余数后继续运算

因此,可以通过模运算,在防止溢出的同时不影响计算结果。

最终答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main()
{
int n,x;
scanf("%d", &n);
int pell[999999+1];
int result[100000];
for (int i=1; i<=n; ++i)
{
scanf("%d", &x);
pell[1]=1;
pell[2]=2;
for (int j=3; j<=x; ++j)
{
pell[j]=pell[j-1]*2+pell[j-2];
pell[j] %= 32767;
}
result[i]=pell[x];
}
for (int i=1; i<=n; ++i)
{
printf("%d\n", result[i]);
}
return 0;
}
开往-友链接力
A member of 开往-友链接力

This site was deployed by @OasisLee using Stellar.

本站由Vercel提供托管与Serverless支持 | PlanetScale提供数据库支持