[cnoier]斐波那契数

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 fibonacci.in 输出文件 fibonacci.out

题目描述

小X 是个聪明的孩子,他记得斐波那契数列

\[ \begin{array}{ll} f(x)=f(x-1)+f(x-2) & x>2 \\ f(x)=1 & 0 < x \le 2 \end{array} \]

中前1000个数。不过由于学业的压力,他无法记得每一个数在数列中的位置。他现在知道数列中的一个数f(x)模P后的值N(即N=f(x)ModP)以及x可能的最大值M,如果再对于斐波那契数列中每一个数都模P,他想知道所知道的这个数可能出现在第几个。不过小X 还要做作业呢,这个问题就交给你由编程来解决了。

输入

一行,共3个整数,第一个数为N,第二个数为P,第三个数为M,三个数以空格隔开。

输出

一个整数,满足f(i)ModP=N的最小的i,如果不存在则输出-1。

样例输入

3 7 5

样例输出

4

提示

斐波那契数列前5项为1 1 2 3 5,全部模7后仍为1 1 2 3 5,则3最早出现在第4个,即满足f(x) ≡ N(ModP)的最小的x为4。

【数据范围与约定】

对于20%的数据,保证0<M≤50

对于50%的数据,保证0<M≤100

对于70%的数据,保证0<M≤500

对于100%的数据,保证0<M≤1000,0≤N

请注意,最终评测采用文件读写。输入输出文件名在输入输出格式中有

请注意查看答疑贴,程序请发到邮箱,最后统一评测