Pell数列

题目描述

Pell 数列定义为 $a_1=1$ ， $a_2=2$ ， $a_n=2a_{n-1}+a_{n-2}$ （ $n>2$ ）。输入 $n$ 组正整数 $k$ （ $1\leqslant k<1000000$ ），输出 $a_k\bmod 32767$ 。

思路

利用同余封闭性先递推打表到所有询问的最大 $k$ ，每组询问直接 $O(1)$ 查表输出。

参考代码

Python 版：

python

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
26
27
28
29
30
31#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-29 23:15
# update_at: 2026-09-29 23:15

import sys

MOD = 32767  # 题面给定的模数


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)
    ks = [next(data) for _ in range(T)]  # 所有询问的 k，先读入再一起回答

    # Pell 数列前 max(ks) 项整体取模：递推只涉及加法和乘法，模运算下保持一致
    limit = max(ks)
    pell = [0] * (limit + 1)
    pell[1] = 1 % MOD
    if limit >= 2:
        pell[2] = 2 % MOD
    for i in range(3, limit + 1):
        pell[i] = (2 * pell[i - 1] + pell[i - 2]) % MOD

    print('\n'.join(str(pell[k]) for k in ks))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 05:27
 * update_at: 2026-10-05 05:27
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 1000005; // k < 1000000，留足余量
const int MOD = 32767;

int p[MAXN]; // p[i] 表示 Pell 数列第 i 项模 32767 的值，值域 [0, 32766]，用 int 即可
int q[MAXN]; // 所有询问的 k

int main() {
    int n;
    scanf("%d", &n);

    int L = 0; // 询问中最大的 k
    for (int i = 0; i < n; i++) {
        scanf("%d", &q[i]);
        if (q[i] > L) L = q[i];
    }

    p[1] = 1;
    p[2] = 2;
    for (int i = 3; i <= L; i++) {
        p[i] = (2 * p[i - 1] + p[i - 2]) % MOD;
    }

    for (int i = 0; i < n; i++) {
        printf("%d\n", p[q[i]]);
    }

    return 0;
}

目录

题目描述

思路

参考代码