洛谷 - P4994 终于结束的起点

题面

难度:普及-
标签:递推 枚举,暴力 斐波那契

题目描述

广为人知的斐波拉契数列 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)modM\mathrm{fib}(n - 1) \bmod M) 和 (fib(n2)modM)\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)modM=0,fib(n+1)modM=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

代码

#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;
}
洛谷 - P4994 终于结束的起点
本文作者
宝硕
发布于
2020-10-03
更新于
2021-07-15
许可协议
喜欢这篇文章?为什么不考虑打赏一下作者呢?
爱发电
文章目录
  1. 题面
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 输入输出样例
  2. 思路
  3. 代码