洛谷 - P4994 终于结束的起点

#题面

#题目描述

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

$$fib(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, \ldots$，每一项都是前两项之和。

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

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

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

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

#输入格式

输入一行一个正整数 $M$ 。

#输出格式

输出一行一个正整数 $n$ 。

#输入输出样例

输入 #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;
}