06/04/2025 18:15:22

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

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

Задачи

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

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

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

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

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

Задачи

2568. Треугольник Штерна

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

Треугольник Штерна строится следующим образом. $n$ -я строка содержит $2^n-1$ элементов Обозначим значение $k$ -го элемента в $n$ -й строке как $S(n, k)$ . Будем считать, что $S(n, k) = 0$ если $k = 0$ или $k = 2^n$ . Тогда
$S(1, 1) = 1$
$S(n+1, 2*k) = S(n, k)$ для $n >= 1$
$S(n+1, 2*k+1) = S(n, k) + S(n, k+1)$ .

Первые 6 строк треугольника Штерна выглядят так:

1
1 1 1
1 1 2 1 2 1 1
1 1 2 1 3 2 3 1 3 2 3 1 2 1 1
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 4 3 5 2 5 3 4 1 3 2 3 1 2 1 1
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 2 7 5 8 3 7 4 5 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 4 3 5 2 5 3 4 1 3 2 3 1 2 1 1

При достаточно большом $n$ $S(n+1,k)=S(n,k)$ .

Рассмотрим предельную последовательность $B(k)=lim_{n->oo} S(n,k)$ .

Можно доказать, что для любого рационального положительного числа $p/q$ , где $gcd(p,q)=1$ , существует ровно одно $k$ , такое что $p/q={B(k)}/{B(k+1)}$ . Например, $3/5={B(10)}/{B(11)}$ .

Напишите программу, которая находит заданное рациональное число в последовательности $B(k)$ .

Первая строка ввода содержит два взаимно простых целых числа $p$ и $q$ ( $1 <= p, q <= 200000$ ).

Вывести одно целое число – номер элемента $k$ по модулю $1 000 000 007$ .

Пример ввода 1

3 5

Пример вывода 1

Пример ввода 2

123 67

Пример вывода 2