Codeforces Round 122 (Div. 1) |
---|
Закончено |
У Джона Доу есть список всех чисел Фибоначчи по модулю 1013. Этот список бесконечен, он начинается с чисел 0 и 1. Каждое число в этом списке, кроме двух первых, является суммой двух предыдущих по модулю 1013, то есть список Джона получается из списка чисел Фибоначчи заменой каждого числа в нем его остатком от деления на 1013.
Теперь Джон загадал число f (0 ≤ f < 1013), и хочет найти его первое вхождение в описанный выше список. Помогите Джону, найдите номер первого вхождения числа 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.
Выведите единственное число — номер первого вхождения заданного числа в список Джона или -1, если это число не входит в список Джона.
13
7
377
14
Название |
---|