← 返回题目列表

Codeforces · 193/E

E. 斐波那契数

中文机器翻译题面 查看原题

John Doe 有一个以 1013 为模的所有斐波那契数的列表。这个列表是无限的,以数字 0 和 1 开始。列表中的每个数字(除了前两个)都是前两个模 1013 的和。也就是说,John 的列表是根据斐波那契数列表中的每个数字替换为除以 1013 时的余数而得出的。

John 对数字 f (0 ≤ f < 1013) 感兴趣,现在想要找到它在上面给出的列表中的第一次出现。帮助 John 找到数字 f 在列表中第一次出现的数字,或者说明数字 f 在列表中没有出现。

约翰的列表中的编号从零开始。其中,第 0 个位置是数字 0,第 1 个位置是数字 1,第 2 个位置是数字 1,第 3 个位置是数字 2,第 4 个位置是数字 3,依此类推。因此,列表的开头如下所示:0, 1, 1, 2, 3, 5, 8, 13, 21, ...

输入

第一行包含单个整数 f (0 ≤ f < 1013) — 数字,我们应该在列表中找到哪个位置。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

输出

打印单个数字 — 给定数字在 John 的列表中第一次出现的数字。如果该数字没有出现在 John 的列表中,则打印 -1。

示例

输入 #1

13

输出 #1

7

输入 #2

377

输出 #2

14