Превращение числа

Обозначим через L наименьшее общее кратное всех чисел от 2 до k. Заметим, что если a кратно L, то мы не сможем уменьшить его операцией второго типа. А это значит, что в оптимальной последовательности превращений будут присутствовать все числа, кратные L, которые находятся между b и a. Разобьем все числа от b до a на отрезки между числами, кратными L. Может выйти так, что первый и последний отрезки будут не полными. Видно, что достаточно решить задачу для первого и последнего отрезка, а также решить задачу для любого отрезка между ними, после чего последний результат нужно еще умножить на количество отрезков между крайними. Осталось только сложить полученные 3 числа и вывести ответ.

Также требовалось аккуратно рассмотреть случаи, когда у нас есть всего 1 или 2 отрезка.

Сложность решения O(L).