В этой версии вам нужно реализовать часть чекера для конструктивной версии.
В этой версии вы ogiyo.
kijjot дает вам два целых числа $$$a$$$ и $$$b$$$ такие, что $$$a \le b$$$. За одну операцию вы можете выбрать такое положительное целое число $$$x$$$, что $$$\gcd(a, x) = 1$$$$$$^{\text{∗}}$$$, после чего увеличить $$$a$$$ на $$$x$$$.
Ваша задача — найти любую последовательность операций минимальной возможной длины для преобразования $$$a$$$ в $$$b$$$. Можно показать, что при заданных ограничениях всегда можно превратить $$$a$$$ в $$$b$$$ не более чем за $$$15$$$ операций.
$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Каждый набор входных данных содержит два целых числа $$$a$$$ и $$$b$$$ ($$$2 \le a \le 10^5$$$, $$$a \le b \le 10^9$$$) — числа, переданные вам kijjot.
Для каждого набора входных данных в первой строке выведите минимальное количество операций $$$k$$$ ($$$0 \le k \le 15$$$).
Во второй строке выведите $$$k$$$ положительных целых чисел $$$x_1, x_2, \ldots, x_k$$$ — значения $$$x$$$, выбранные в операциях, в порядке их выполнения. Эти операции должны быть допустимыми и превращать $$$a$$$ в $$$b$$$.
Если $$$k = 0$$$, вторую строку можно не выводить. Если существует несколько оптимальных последовательностей, выведите любую из них.
4 2 2 15 25 2184 2200 100000 1000000000
0 2 1 9 3 11 2 3 2 1636673 998263327
В первом наборе входных данных $$$a = b = 2$$$, поэтому операции не нужны.
Во втором наборе входных данных можно сначала прибавить $$$1$$$ и получить $$$16$$$, а затем прибавить $$$9$$$ и получить $$$25$$$. Обе операции допустимы, поскольку $$$\gcd(15, 1) = 1$$$ и $$$\gcd(16, 9) = 1$$$. Можно показать, что менее $$$2$$$ операций недостаточно.
| Codeforces Round 1132 (Div. 2) |
|---|
| Закончено |
