Преобразование моноклеточных
(Время: 1 сек. Память: 16 Мб Сложность: 29%)
Как великолепна страна Байтландия! В ней есть цветущие леса, прозрачные реки, кисельные берега… Но речь пойдет не о них. Уже много лет в Байтландии функционирует НИИ “Цитологии и генетики”. В нем выводятся новые формы жизни. Недавно ученым этого НИИ удалось разработать принципиально новый вид организмов. Особенностью этих организмов является то, что они состоят из большого количества однотипных клеток, то есть являются моноклеточными.
Правительство Байтландии заинтересовалось новой разработкой и сделало заказ на производство двух моноклеточных организмов, в каждом из которых должно быть по M клеток. За несколько дней до сдачи проекта было обнаружено, что в одном из организмов получается не M клеток, а N. На какой из стадий разработки была допущена ошибка неизвестно, но положение надо исправлять!
Сотрудниками НИИ было принято решение о преобразовании моноклеточного с N клетками в моноклеточное с M клетками. Для этого в экстренном режиме было разработано два типа вещества:
- Вещество, которое делит клетки моноклеточного организма, т.е. каждая клетка делится на P частей. В результате количество клеток умножается на P, где P – простое число.
- Вещество, объединяющее клетки. Клетки организма объединяются в группы по T штук, где Т также простое число. Далее каждая группа клеток объединяется в одну клетку. В результате общее количество клеток делится на T. При этом T выбирается таким, чтобы деление происходило без остатка.
Отметим, что натуральное число называется простым, если оно имеет только два натуральных делителя – это единица и само число.
Серьезным недостатком этих веществ является их высокая стоимость. В соответствии с этим требуется преобразовать моноклеточное с N клетками в моноклеточное с M клетками за минимальное количество операций. За одну операцию к моноклеточному можно применить одно вещество из двух заданных типов. Помогите НИИ “Цитологии и генетики” разрешить эту непростую задачу!
Входные данные
В первой строке входного файла INPUT.TXT заданы два натуральных числа N и M (1 ≤ N, M ≤ 109) разделенные одиночным пробелом.
Выходные данные
Единственная строка выходного файла OUTPUT.TXT должна содержать целое число – минимальное количество операций, необходимое для преобразования моноклеточного организма с N клетками в моноклеточный организм с M клетками.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 36 | 3 |
| 2 | 32768 3 | 16 |
| 3 | 1434 1434 | 0 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
