题解 P4994 【终于结束的起点】

· · 题解

核心思路（个人不喜认真写题解，一认真语句就拖拉啰嗦，不如随性写题解，希望大家能看懂）

1.首先，一个while循环和计数变量n肯定少不了

2.斐波拉契数列是一个递推数列，并且第三项开始，该项大小为前二项之和。 据此，我们开出三个变量f0,f1,f2，f0与f1初始值分别为0,1。这样，我们就可以愉快得递推数列了f2=f0+f1

3.由(x%m+y%m)%m=(x+y)%m这一基本定理（没说错吧……不管了）可知，直接取模并不影响我们对于数列的递推，于是，我们愉快地对f2直接取模f2=f2%m

4.既然已经取模了，那我们就可以愉快得直接判断f1==0&&f2==1，不需要反复去模或者对很大的数进行运算，可以降低时间复杂度。判断对了，我们就愉快地输出，然后return 0直接结束程序

5.判断错后，我们要为下一次循环的递推做准备，这时，f0已经没有用了，于是我们把原本f1与f2的值赋到f0月f1上，空出f2的位置等下一次循环递推

6.哦，别忘了n++

核心思路讲完了，我们愉快地贴代码，看不懂的别愉快地复制粘贴，推一下就好

#include<iostream>
#include<cstdio>
using namespace std;
int m,n=1,i,f1=0,f2=1,f3; 
int main(){
    scanf("%d",&m);
    while(1){
        f3=(f1+f2)%m;
        if(f2==0&&f3==1){
            printf("%d",n);
            return 0;
        }
        f1=f2;f2=f3;
        n++;
    }
    return 0;
}