落谷----P4994 终于结束的起点
在这里插入图片描述
在这里插入图片描述
终于结束的起点题解集合
递推
思路:
首先无论取什么模数 M，最终模 M 下的斐波拉契数列都会是 0, 1, …, 0, 1, …
我们需要求出: 请你求出最小的 n > 0，使得 fid(n) mod M=0,fib(n+1) mod M=1;
例如:
在这里插入图片描述
其实本题本质还是不断递推求出fib数列每一项的值，求的同时对M进行取模，然后判断当前取模得出的结果是否为0，并且同时下一位对M取模得出的结果应该为1
我们设3个变量f[0] f[1] temp
- f[0]记录当前斐波那契数列的值
- f[1]记录下一个的值
- temp用作更新用的值（辅助变量）
下面是更新操作（滚存）
在每一次循环中，我们做到
int temp = dp[0];
dp[0] = dp[1];
dp[1] = (temp + dp[1]) % M;代码:
#include<iostream>
using namespace std;
class Solution
{
public:
int solution(int M)
{
int dp[2] = { 0,1 };
for (int i = 1;; i++)
{
int temp = dp[0];
dp[0] = dp[1];
dp[1] = (temp + dp[1]) % M;
if (dp[0] % M == 0 && dp[1] % M == 1) return i;
}
}
};
int main()
{
Solution s;
int n, M;
cin>> M;
cout<<s.solution(M)<<endl;
return 0;
}
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/06/02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
