P4994 终于结束的起点

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

Solution

\(NOIp\) 之前要搞点这种题找自信的啊

此题直接枚举即可

优化空间滚动数组即可

然而上考场我们不能这么就完了

应该打表看看循环节与 \(M\) 的关系

在发现 \(M\) 与其循环节相差不大， 估算出复杂度再打

不然就打完暴力， 看完其他题在回来想正解

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

int M;

int n[7];

void init(){

	M = RD();

	n[0] = 0;

	n[1] = 1;

	}

void solve(){

	int now = 1;

	while(1){

		int temp = (n[0] + n[1]) % M;

		if(temp == 1 && n[1] == 0){

			printf("%d\n", now);

			return ;

			}

		n[0] = n[1];

		n[1] = temp;

		now++;

		}

	}

int main(){

	init();

	solve();

	return 0;

	}