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<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<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