21/11/2024 20:15:30

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2806. Золушка и числа Фибоначчи

Ограничения: время – 250ms/600ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Cлучилось однажды, что король затеял бал, который должен был длиться целых три дня, и созвал на праздник всех
красивых девушек страны, с тем чтобы сын его мог выбрать себе невесту.
Золушке тоже хотелось пойти на бал; она стала просить мачеху, чтобы та отпустила ее.

Мачеха не хотела, чтобы Золушка попала на бал, поэтому задала ей такую сложную задачу, с которой не справился бы даже знаменитый математик Гаусс:

-- Найди сумму остатков от деления первых `N` чисел Фибоначчи на число `M`. Коли справишься за два часа, тогда можешь идти вместе с сестрами.

Числа Фибоначчи определяются следующим образом `F_0=0`, `F_1=1`, `F_i=F_{i-1}+F_{i-2}`, где `i>=2`.

Необходимо найти `sum_{i=0}^{i<N} (F_i mod M)`.

`i` |0|1|2|3|4|5|6|7 |8 |9
-----------|-|-|-|-|-|-|-|--|--|--
`F_i` |0|1|1|2|3|5|8|13|21|34
`F_i mod 4`|0|1|1|2|3|1|0|1 |1 |2

Напишите программу, которая поможет Золушке найти эту сумму как можно быстрее.

Первая строка ввода содержит два целых числа `M` (`2<=M<=10^6`) и `N` (`1<=N<=10^12`).

Вывести одно целое число -- искомую сумму.

```sample Пример ввода 1
4 10
```

```sample Пример вывода 1
12
```

```sample Пример ввода 2
10 100
```

```sample Пример вывода 2
470
```

В 60% тестов `N<10^6`.

19/09/2024	Отборочный тур личных соревнований (A)
30/09/2024	Дорешивание личных соревнований (2+ курсы) (проводит BOGAT) (E)
02/10/2024	Дорешивание личных соревнований (1 курс) (проводит BOGAT) (E)