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

本文主要是介绍【题解】P4994 终于结束的起点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

百年更新一次得我

P4994 终于结束的起点题解

原题：

题目背景

终于结束的起点
终于写下句点
终于我们告别
终于我们又回到原点
……

一个个 OIer 的竞赛生涯总是从一场 NOIp 开始，大多也在一场 NOIp 中结束，好似一次次轮回在不断上演。
如果这次 NOIp 是你的起点，那么祝你的 OI 生涯如同夏花般绚烂。
如果这次 NOIp 是你的终点，那么祝你的 OI 回忆宛若繁星般璀璨。
也许这是你最后一次在洛谷上打比赛，也许不是。
不过，无论如何，祝你在一周后的比赛里，好运。

当然，这道题也和轮回有关系。

题目描述

广为人知的斐波拉契数列 $\mathrm{fib}(n)$ 是这么计算的

$$\mathrm{fib}(n)=\{\begin{array}{ll}0,& n=0\\ 1,& n=1\\ \mathrm{fib}(n-1)+\mathrm{fib}(n-2),& n>1\end{array}$$

也就是 $0,1,1,2,3,5,8,13\cdots$，每一项都是前两项之和。

小 F 发现，如果把斐波拉契数列的每一项对任意大于 $1$ 的正整数 $M$ 取模的时候，数列都会产生循环。

当然，小 F 很快就明白了，因为 ($\mathrm{fib}(n-1)\mathrm{mod}M$) 和 ($\mathrm{fib}(n-2)\mathrm{mod}M)$ 最多只有 $M^2$ 种取值，所以在 $M^2$ 次计算后一定出现过循环。

甚至更一般地，我们可以证明，无论取什么模数 $M$，最终模 $M$ 下的斐波拉契数列都会是 $0,1,\cdots ,0,1,\cdots$。

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

输入格式

输入一行一个正整数 $M$。

输出格式

输出一行一个正整数 $n$。

样例 #1

样例输入 #1

2

样例输出 #1

3

样例 #2

样例输入 #2

6

样例输出 #2

24

提示

样例 1 解释

斐波拉契数列为 $0,1,1,2,3,5,8,13,21,34,\cdots$，在对 $2$ 取模后结果为 $0,1,1,0,1,1,0,1,1,0,\cdots$。

我们可以发现，当 $n=3$ 时，$f(n)\mathrm{mod}2=0,f(n+1)\mathrm{mod}2=1$，也就是我们要求的 $n$ 的最小值。

数据范围

对于 $30\%$ 的数据，$M\le 18$；

对于 $70\%$ 的数据，$M\le 2018$；

对于 $100\%$ 的数据，$2\le M\le 706150=\text{0xAC666}$。

提示

如果你还不知道什么是取模 $(\mathrm{mod})$，那我也很乐意告诉你，模运算是求整数除法得到的余数，也就是竖式除法最终「除不尽」的部分，也即
$$a\mathrm{mod}M=k⟺a=bM+k(M>0,0\le k<M)$$
其中 $a,b,k$ 都是非负整数。

如果你使用 C / C++，你可以使用 % 来进行模运算。

如果你使用 Pascal，你可以使用 mod 来进行模运算。

题目大意

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

思路

一开始想找数学方法过
但是后来有一位大佬的分享
就让我想起了滚存

思路是用$f[0],f[1],f[2]$只要给变量就可以进行滚动存储

$f[2]$是一个用来辅助用的数组(有点像我交换时常用的tmp)

$f[0]$是上一个数

$f[1]$是当前数

后来呐？
没后来辣，上代码

代码

int a[N];
int m;
void solve() {int m; cin >> m;a[0] = 0;a[1] = 1;a[2] = 1;for(int i = 1; ; i++){a[2] = a[0];a[0] = a[1];a[1] = (a[2] + a[1]) % m;if (a[0] % m == 0 && a[1] % m == 1){cout << i << endl;return;}}
}

---

拜拜┏(＾0＾)┛

这篇关于【题解】P4994 终于结束的起点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---