YZOJ P4587 斐波那契数列
时间限制：1234MS 内存限制：43210KB
难度：\(6.5\) （既然是自己搬的题还是正常一点吧w）
-
题目描述
定义模意义下的递推数列 \(\displaystyle f_n=\left\{ {\begin{array}{*{20}{c}} 1&{,n \le 2}\\ {{f_{n – 1}} + {f_{n – 2}}}&{,n > 2} \end{array}} \right.\)，其中模数为 \(1000000009\) 。
给定整数 \(c\)（\(0 \leq c < 1000000009\)），求出它最早出现在数列的哪个位置，并输出下标。
若 \(c\) 永远不会出现在此数列的任一位置，则输出 \(-1\) 。
-
输入格式
多组数据。
第一行一个正整数 \(T\) （\(0 < T \leq 100\)） 表示 \(T\) 组数据。
接下来 \(T\) 行每行一个数表示每组数据的 \(c\) 。
-
输出格式
对于每组数据，输出一行一个数表示答案。
-
样例输入
|
1 2 3 |
2 987 321 |
-
样例输出
|
1 2 |
16 -1 |