Цепочка делителей

C. Цепочка делителей
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Дано целое число x. Вам нужно уменьшить x до 1.

Для этого вы можете выполнять следующую операцию несколько (возможно, ноль) раз:

выбрать d, являющееся делителем x, затем заменить x на x−d, т.е. уменьшить x на d. (Мы называем d делителем x, если d — положительное целое число, для которого существует целое q, такое что x=d⋅q.)
Кроме того, есть дополнительное ограничение: вам нельзя выбирать одно и то же значение d более двух раз.

Например, для x=5 следующая последовательность действий является недопустимой, поскольку в ней 1 использована более чем дважды: 5−1→4−1→3−1→2−1→1. Однако следующая последовательность действий является допустимой:5−1→4−2→2−1→1.

Выведите произвольную последовательность действий, которая уменьшает x до 1 не более чем за 1000 операций. Можно доказать, что такая последовательность всегда существует.

Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число t (1≤t≤1000) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит одно целое число x (2≤x≤10⁹).

Выходные данные
Для каждого набора входных данных выведите две строки.

В первой строке выведите целое число k (1≤k≤1001).

Во второй строке через пробел выведите k целых чисел a₁,a₂,…,a_k, таких что:a₁=x;a_k=1;
для каждого 2≤i≤k, величина (a_i−1−a_i) является делителем a_i−1. Каждое число может быть выбрано делителем не более чем дважды.
Пример
входные данные
3
3
5
14
выходные данные
3
3 2 1
4
5 4 2 1
6
14 12 6 3 2 1
Примечание
В первом наборе входных данных можно выполнить следующую последовательность операций: 3−1→2−1→1.

В втором наборе входных данных можно выполнить следующую последовательность операций: 5−1→4−2→2−1→1.

В третьем наборе входных данных можно выполнить следующую последовательность операций: 14−2→12−6→6−3→3−1→2−1→1.

0

Подозреваю (но это не точно), что на каждом этапе нужно брать максимально возможный делитель (ясное дело, он должен быть меньше текущего числа "со всеми вытекающими отсюда моментами").

0

Сообщение от gunslinger на каждом этапе нужно брать максимально возможный делитель (ясное дело, он должен быть меньше текущего числа

максимально возможный делитель это само число, но т.к. вы пишете, что он должен быть меньше текущего числа, то полагаю, вы предлагаете брать предпоследний делитель из списка всех возможных делителей, сортированных по возрастанию.

Но такой подход будет работать не всегда из-за того, что в условии сказано:

Сообщение от chara1221 есть дополнительное ограничение: вам нельзя выбирать одно и то же значение d более двух раз.

В условии сказано, что

Сообщение от chara1221 Единственная строка каждого набора входных данных содержит одно целое число x (2≤x≤10⁹).

И если начать проверку с числа 2 и дальше, то уже видно, что такой подход не работает для чисел:

Ниже привожу числа x, где в фигурных скобках приводятся значения d
7 {1,3,1,1}
11 {1,5,1,2,1}
13 {1,6,3,1,1}
14 {7,1,3,1,1}
19 {1,9,3,3,1,1}
21 {7,7,1,3,1,1}
22 {11,1,5,1,2,1}
23 {1,11,1,5,1,2,1}
и т.д.

Как видно, мы берем d=1 больше двух раз, что противоречит условию. Так получается, когда текущее значение x является простым числом и по алгоритму мы вынужденно берем 1. Для больших значений x в дальнейшем могут повторяться и другие числа.

Например,
49 {7,21,7,7,1,3,1,1}
Тут 3 раза повторяется d=7, и столько же раз повторяется d=1.

1

На примере числа x = 6, можно увидеть возможные ответвления (красным цветом выделены значения d, жирным шрифтом - текущие значения x):



Их 5 штук. Но соответствуют условию только 2 из 5:
1) 3, 1, 1
2) 2, 2, 1
3) 2, 1, 1, 1 не подходит, т.к. 3 единицы
4) 1, 1, 2, 1 не подходит, т.к. 3 единицы
5) 1, 1, 1, 1, 1 не подходит, т.к. 5 единиц

Полагаю, что можно перебирать, пока не найдем последовательность значений d, в которой ни одна из чисел не встречается более двух раз. Причем, имеет смысл начинать перебор с больших делителей. Так быстрее закончится поиск + найдем самое короткое решение.

1

А будь у нас число 7, то для первой операции у нас есть только один вариант d = 1.
7-1=6 и мы снова попадаем на те самые 5 ответвлений числа 6.
Уже знаем, что для 6 подходят только 1-е и 2-е ответвления. Поэтому нашу 1 от первой операции стоит добавить только к этим двум спискам:
1 + 3, 1, 1
1 + 2, 2, 1
Видно, что в первом списке получились 3 единицы и это не подходит.
Поэтому, для числа 7 подходит только 1, 2, 2, 1:
7 - 1 = 6
6 - 2 = 4
4 - 2 = 2
2 - 1 = 1
На примере, числа 7 (и как я писал выше) заметно, что не всегда нужно выбирать вариант с максимальными делителями (без учета самого числа). Ведь, такой вариант 1, 3, 1, 1 для числа 7 не подошел. Тем не менее, повторюсь, что есть логика перебирать с больших делителей.

1

Сначала вычитаем единичные биты (x & (1 << i) != 0) от младшего к старшему, останется 0x10...0, затем делим пополам до конца.

0