递推典型题目P4994题解

原题解发布于7月14日

原题解：

这题看起来很复杂，实际上很简单

让我们把题目先简化一下：

简化题意

给出一个正整数M，求出最小的$n(n>0)$，使$fib(n)\%m=0$，$fib(n+1)\%m=1$。

注：模即C++中的%符号

注意！题目要求fib(n)和fib(n + 1) 都大于1，所以n > 2！

使用方法

1：输入m，开数组

2：循环，计算出fib(i) % m 的值

3：判断条件是否成立，成立则返回

代码：（不能只看这里啊）

/*
提醒：
1、因为这是我在之前的AC代码，所以码风有点老，请见谅
2、直接提交过不了的，别抄代码了
*/
#include <bits/stdc++.h> // 再熟悉不过的头文件
using namespace std;
int a[1000005]; // 假设n < 1e7
int main(){
    int m; // 题目已给
    scanf("%d", m);
    a[0] = 0;
    a[1] = 1;
    for(int i = 3;i < 1000000;i++){ // 注意从3开始
        a[i] = a[i - 1] + a[i - 2]； // 计算该值,为防越界每次都%m
        if(a[i - 1] == 0 && a[i] = 1){ // 判断条件
            cout << i - 1;
        }
    return 0; // 好习惯
}