自动搬运

查看原文

来自洛谷，原作者为

	owowow 最后在线时间：2025/8/4 7:32

搬运于2025-08-24 23:03:44，当前版本为作者最后更新于2024-09-11 13:19:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11042 类斐波那契循环数题解

题目大意

对于一个有 $n$ 位的十进制数 $N = d_1d_2d_3\dots d_n$，可以生成一个类斐波那契数列 $S$。

数列 $S$ 的前 $n$ 个数为 $\{S_1=d_1,S_2=d_2,S_3=d_3,\dots,S_n=d_n\}$，数列 $S$ 的第 $k(k>n)$ 个数为 $\sum^{k−1}_{i=k−n} S_i$。

如果这个数 $N$ 会出现在对应的类斐波那契数列 $S$ 中，那么 $N$ 就是一个类斐波那契循环数。 求小于 $10^7$ 的最大的类斐波那契循环数是多少。

题目思路

直接暴力搜索 $n$，每一次用一个函数 pd(i) 来判断 $n$ 是否为类斐波那契循环数。

接下来详细说说 pd(i) 的写法。

首先定义数组 $a$，$a_i=d_i$。数组 $b$ 的前 $n$ 个数为对应下标的 $a_i$。也就是说，$b_i=a_i (i \le n)$。

对于后面的 $b_i$，$b_i=\sum^{i-1}_{j=i-1-n}b_j$。如果 $b_i=n$，那么 $n$ 就是类斐波那契循环数。

判断代码：

def pd(x):
    s=str(x)
    n=len(s)
    a=[]
    for i in range(n):
        a.append(int(s[i]))
    b=a
    while 1==1:
        t=0
        for i in range(len(b)-n,len(b)):
            t+=b[i]
        if t>10000000 :
            return 0
        if t==x:
            return 1
        b.append(t)

正确代码

def pd(x):
    s=str(x)
    n=len(s)
    a=[]
    for i in range(n):
        a.append(int(s[i]))
    b=a
    while 1==1:
        t=0
        for i in range(len(b)-n,len(b)):
            t+=b[i]
        if t>10000000 :
            return 0
        if t==x:
            return 1
        b.append(t)


for i in range(10000000, 0, -1):
    if pd(i) == 1:
        print(i)
        break

结果输出 $7913837$，那么答案就是 $7913837$。

AC 代码

print(7913837)