[洛谷月赛]终于结束的起点

题目背景

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

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

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

---

题目描述

广为人知的斐波拉契数列fib(n) 是这么计算的:

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

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

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

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

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

输入

输入一行一个正整数 M。

输出

输出一行一个正整数n。

样例组

样例1
输入 2
输出 6
 
样例2
输入 6
输出 24

---

解题思路

        (本来写了两千字的，结果没保存，......)

        首先，这道题目不需要打表找规律，可以使用记忆化搜索或者递推来解决。

        但是由于没有保存，再加上发现的时候已经快晚上十一点了，没办法，这里只好补一些核心程序了。(愿见谅)

        记忆化搜索主程序如下：

int f[10000001],n;
void dfs(int n)
{
    if(f[i]!=0) return f[i];
    else return dfs(n-1)+dfs(n-2);//空间换时间
}

        赋初值代码段如下： 

f[0]=f[1]=1;//等价于f[0]=1;f[1]=1;

        递推做法递推式如下：

a[i]=(a[i-1]+a[i-2])%n;

---

AC代码

        递推做法：

#include
#define N 7061500
using namespace std;
int n,a[N];
int main()
{
	cin>>n;a[1]=a[0]=1;
	for(int i=2;;i++)
	{
		a[i]=(a[i-1]+a[i-2])%n;
		if(a[i]%n==1&&a[i-1]%n==0)
		{
			cout<"\n";
			break;
		}
	}
	return 0;
}

        记忆化搜索做法： 

#include
#define N 7061500
using namespace std;
int n,a[N];
void dfs(int n)
{
    if(f[i]!=0) return f[i];
    else return dfs(n-1)+dfs(n-2);
}
int main()
{
	cin>>n;a[1]=a[0]=1;
	for(int i=2;;i++)
	{
		a[i]=dfs(i);
		if(a[i]%n==1&&a[i-1]%n==0)
		{
			cout<"\n";
			break;
		}
	}
	return 0;
}

        这道题目就这么多。