[Luogu]P4994

发表于 更新于 分类于

原题：终于结束的起点

分析

枚举n…判断是否满足$\mathrm{fib}(n) \bmod M = 0, \mathrm{fib}(n + 1) \bmod M = 1$

不过如果直接模拟的话，可能会爆空间

于是进行一个小小的优化：

迭代！

我们可以令$f0=0,f1=1;$

然后在递推的时候$f2=(f0+f1) \bmod M;$

然后迭代：$f0=f1,f1=f2;$

就可以极大地节省空间！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long m;
int main()
{
    cin>>m;
    int f0=0,f1=1;
    for(long long i=1;i<=m*m+1;++i) {
        int f2=(f1+f0)%m;
        if(f2==1 && f1==0) {
            cout<<i;
            return 0;
        }
        f0=f1;f1=f2;
    }
    return 0;
}