301025: CF193E. Fibonacci Number

Memory Limit:256 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Fibonacci Number

题意翻译

# 题目描述 斐波那契数列对10^13取模的定义如下:   1、F0 = 0, F1 = 1   2、Fi = (Fi-1 + Fi-2) mod (10^13) (i >= 2)   输入一个数x,问x是否在斐波那契数列当中出现过,如果出现过,最早出现在哪个位置。 # 输入格式 一行,一个整数x。 # 输出格式 一行,表示x在数列中最早出现的位置,如果没有出现过,则输出-1。

题目描述

John Doe has a list of all Fibonacci numbers modulo $ 10^{13} $ . This list is infinite, it starts with numbers $ 0 $ and $ 1 $ . Each number in the list, apart from the first two, is a sum of previous two modulo $ 10^{13} $ . That is, John's list is made from the Fibonacci numbers' list by replacing each number there by the remainder when divided by $ 10^{13} $ . John got interested in number $ f $ ( $ 0<=f&lt;10^{13} $ ) and now wants to find its first occurrence in the list given above. Help John and find the number of the first occurence of number $ f $ in the list or otherwise state that number $ f $ does not occur in the list. The numeration in John's list starts from zero. There, the $ 0 $ -th position is the number $ 0 $ , the $ 1 $ -st position is the number $ 1 $ , the $ 2 $ -nd position is the number $ 1 $ , the $ 3 $ -rd position is the number $ 2 $ , the $ 4 $ -th position is the number $ 3 $ and so on. Thus, the beginning of the list looks like this: $ 0,1,1,2,3,5,8,13,21,... $

输入输出格式

输入格式


The first line contains the single integer $ f $ ( $ 0<=f&lt;10^{13} $ ) — the number, which position in the list we should find. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出格式


Print a single number — the number of the first occurrence of the given number in John's list. If this number doesn't occur in John's list, print -1.

输入输出样例

输入样例 #1

13

输出样例 #1

7

输入样例 #2

377

输出样例 #2

14

Input

题意翻译

# 题目描述 斐波那契数列对10^13取模的定义如下:   1、F0 = 0, F1 = 1   2、Fi = (Fi-1 + Fi-2) mod (10^13) (i >= 2)   输入一个数x,问x是否在斐波那契数列当中出现过,如果出现过,最早出现在哪个位置。 # 输入格式 一行,一个整数x。 # 输出格式 一行,表示x在数列中最早出现的位置,如果没有出现过,则输出-1。

加入题单

上一题 下一题 算法标签: