Skip to content

洛谷 - P4994 终于结束的起点

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

广为人知的斐波拉契数列 fib(n)\mathrm{fib}(n) 是这么计算的:

fib(n)={0,n=01,n=1fib(n1)+fib(n2),n>1fib(n) = \left \{ \begin{array}{lc} 0, &n=0 \\ 1, &n=1 \\ fib(n-1)+fib(n-2), &n>1 \end{array} \right.

也就是 0,1,1,2,3,5,8,13,0, 1, 1, 2, 3, 5, 8, 13, \ldots,每一项都是前两项之和。

小 F 发现,如果把斐波拉契数列的每一项对任意大于 11 的正整数 MM 取模的时候,数列都会产生循环。

当然,小 F 很快就明白了,因为 (fib(n1) mod M\mathrm{fib}(n - 1) \bmod M) 和 (fib(n2) mod M)\mathrm{fib}(n - 2) \bmod M) 最多只有 M2M ^ 2 种取值,所以在 M2M ^ 2 次计算后一定出现过循环。

甚至更一般地,我们可以证明,无论取什么模数 MM,最终模 MM 下的斐波拉契数列都会是 0,1, ,0,1,0, 1, \cdots, 0, 1, \cdots

现在,给你一个模数 MM,请你求出最小的 n>0n > 0,使得 fib(n) mod M=0,fib(n+1) mod M=1\mathrm{fib}(n) \bmod M = 0, \mathrm{fib}(n + 1) \bmod M = 1

#输入格式

输入一行一个正整数 MM

#输出格式

输出一行一个正整数 nn

#输入输出样例

输入 #1

2

输出 #1

3

输入 #2

6

输出 #2

24

#思路

暴力+优化 = AC

#代码

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
#include <bits/stdc++.h>

using namespace std;

long long a[10000000];

long long dfib(long long x, long long m) {
if (a[x] != -1) {
return a[x];
}
if (x == 0) {
a[x] = 0 % m;
return 0;
}
if (x == 1) {
a[x] = 1 % m;
return 1;
}
a[x] = (dfib(x - 1, m) + dfib(x - 2, m)) % m;
return a[x];
}

int main() {
long long m;
memset(a, 0xff, sizeof(a));
cin >> m;
for (int i = 2; i < m * m; i++) {
if (dfib(i, m) == 0 && dfib(i + 1, m) == 1) {
cout << i << endl;
break;
}
}
return 0;
}