print2159. Химеры

printХимеры

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

Однажды, в один из бесконечных тоскливых осенних вечеров, прославленный рыцарь сэр Петрейн отчаянно скучал и вдруг подумал о том, что давненько не навещал своего старого друга Темного Властелина. Еще бы – ведь живет Темный Властелин на вершине Самой Высокой Башни Самого Темного Замка за тысячи верст от мест, где проживают жалкие людишки. Но это еще полбеды, даже треть беды. Основная проблема заключается в том, что к замку Темного Властелина можно попасть только пройдя по длинной узкой Темной Тропке через Темный Лес, вдоль которой Темный Властелин расселил весьма недружелюбно настроенных химер.
Про химер Петрейну известно следующее. У химеры одна голова, но если ее срубить, на ее месте вырастут две новые. Если срубить эти две, то на месте каждой из них вырастет по три новых, на месте этих могут вырасти четыре и так далее. Однако если возраст химеры `n` лет, то у нее не может вырасти больше `n` голов на месте какой-либо срубленной. Формально это можно описать так. Сопоставим каждой голове некоторое число – так называемое поколение. Тогда для химеры, возраст которой составляет `n` лет, справедливо следующее:
  • изначально у химеры одна голова первого поколения;
  • если срубить голову `k`-го поколения, где `1\ ≤\ k\ <\ n`, то на ее месте вырастут `(k\ +\ 1)` голова `(k\ +\ 1)`-го поколения;
  • если срубить голову `n`-го поколения, то на ее месте уже ничего не вырастает.
Можно заметить, что число голов в `k`-м поколении равно `k!\ =\ 1\ *\ 2\ *\ …\ *\ (k\ -\ 1)\ *\ k`. Обозначим как `S(n)` число голов, которое таким образом нужно отрубить `n`-летней химере, чтобы новые перестали вырастать. Например, `S(3)\ =\ 9`. После того, как химере отрубят все `S(n)` голов, она погибает. Если, правда, не случится такое, что `S(n)` вдруг поделится на ее возраст `n`. Потому что тогда лишенная всех голов химера превращается в огромного жирного тролля, от которого проблем просто не оберешься, и ничто его не берет, кроме волшебной стрелы. Так что придется Петрейну на всякий случай запастись волшебными стрелами.
Сэр Петрейн знает, что все химеры в лесу разного возраста, самой юной химере `a` лет, самой старой – `b` лет, и для любого такого числа `x`, что `a\ ≤\ x\ ≤\ b`, в лесу найдется химера с возрастом `x`. Для расправы с каждой химерой, чей возраст является таким числом `n`, что `S(n)` делится на `n`, нужна волшебная стрела. Помогите Петрейну выяснить, сколько стрел ему нужно взять с собой.
Во входном файле даны два целых числа `a` и `b` (`1\ ≤\ a\ ≤\ b\ ≤\ 1000`).
В выходной файл выведите единственное число, равное числу волшебных стрел, которые понадобятся сэру Петрейну на пути к замку Темного Властелина.

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

1 10

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

3

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

2 2

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

0
Источник: neerc.ifmo.ru/school
loading