Олимпиадный тренинг

Задача . Тройной Фибоначчи


Задача

Темы: Остатки
Пятиклассник Лёня недавно прочитал статью о числах Фибоначчи.

Числами Фибоначчи называется числовая последовательность F1 , F2 , ..., Fn , ... , которая устроена следующим образом: F1 = 1 , F2 = 2 , а каждое следующие число вычисляется как сумма двух предыдущих: если i ≥ 3 , то Fi = Fi - 1 + Fi - 2 . Последовательность чисел Фибоначчи, таким образом, начинается с чисел 1, 2, 3, 5, 8, 13, 21, ... .

Сегодня Лёня изучает числа Фибоначчи с номерами от L до R , включительно. Так как Лёня очень любит число 3, ему стало интересно, сколько чисел Фибоначчи среди тех, которые он изучает сегодня, делятся на 3. Например, если L = 3 и R = 7 , то Лёня будет изучать числа F3 = 3 , F4 = 5 , F5 = 8 , F6 = 13 и F7 = 21 . Среди них на 3 делятся два числа: F3 = 3 и F7 = 21 .

Напишите программу, которая поможет Лёне найти ответ на волнующий его вопрос.

Входные данные
Первая строка входных данных содержит число L , а вторая — число R ( 1 ≤ L ≤ R ≤ 105 ).

Выходные данные
Выведите единственное число — количество чисел Фибоначчи с номерами от L до R , включительно, которые делятся на 3.
 
Входные данные Выходные данные
1 3
7
2

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w647
Python2
Комментарий учителя