求赞,求回复,求关注~

题目:https://www.luogu.org/problemnew/show/P4994

这道题和斐波那契数列的本质没有什么区别。。。

分析:

这道题应该就是一个斐波那契数列的计算吧,为了防止数字过大,我们可以每次%m;

为了防止时间过长,我们可以用递推;

为了防止数组开炸,我们可以只记录当前和上一项;

于是这道题听说还是一道原题?但赛后去看了看,真的比原题水一些呀。

代码:

#include<cstdio>
using namespace std;
int main()
{
	int m;	
	scanf("%d",&m);
	int last=0,now=1,tmp;//now用来记录当前更新的一个,last记录上一个(为了能更新下面的项),tmp临时存储当前项,防止被下一项冲掉
	for(int i=2;;i++)
	{
		tmp=now%m;
		now=(now+last)%m;
		last=tmp%m;//每次取模,**(此处被河蟹)再也不用担心我的高精!
		if(last==0&&now==1)//根据题目判断
		{
			printf("%d\n",i-1);//别忘了是第i-1项哦
			break;//找到答案,当然跳出
		}
	}
	return 0;
} 

别走呀!

根据蒟蒻神仙的推理,还推出了一个并没有啥用的东西:

只要当前这一项是m的倍数,那么一定是要找的答案。

推导过程有点冗长,在这里不加赘述,有兴趣的同学可以跟我探讨哦!

主要是也没必要用到这个呀

求赞,求回复,求关注~