Divisor Chain (Codeforces 1864C)
Tags: Math, number theory

You are given an integer $$$x$$$. Your task is to reduce $$$x$$$ to $$$1$$$.To do that, you can do the following operation:  select a divisor $$$d$$$ of $$$x$$$, then change $$$x$$$ to $$$x-d$$$, i.e. reduce $$$x$$$ by $$$d$$$. (We say that $$$d$$$ is a divisor of $$$x$$$ if $$$d$$$ is an positive integer and there exists an integer $$$q$$$ such that $$$x = d \cdot q$$$.) There is an additional constraint: you cannot select the same value of $$$d$$$ more than twice.For example, for $$$x=5$$$, the following scheme is invalid because $$$1$$$ is selected more than twice: $$$5\xrightarrow{-1}4\xrightarrow{-1}3\xrightarrow{-1}2\xrightarrow{-1}1$$$. The following scheme is however a valid one: $$$5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1$$$.Output any scheme which reduces $$$x$$$ to $$$1$$$ with at most $$$1000$$$ operations. It can be proved that such a scheme always exists.

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.The only line of each test case contains a single integer $$$x$$$ ($$$2\le x \le 10^{9}$$$).

Output: For each test case, output two lines.The first line should contain an integer $$$k$$$ ($$$1 \le k \le 1001$$$).The next line should contain $$$k$$$ integers $$$a_1,a_2,\ldots,a_k$$$, which satisfy the following:  $$$a_1=x$$$;  $$$a_k=1$$$;  for each $$$2 \le i \le k$$$, the value $$$(a_{i-1}-a_i)$$$ is a divisor of $$$a_{i-1}$$$. Each number may occur as a divisor at most twice. 

Note: In the first test case, we use the following scheme: $$$3\xrightarrow{-1}2\xrightarrow{-1}1$$$.In the second test case, we use the following scheme: $$$5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1$$$.In the third test case, we use the following scheme: $$$14\xrightarrow{-2}12\xrightarrow{-6}6\xrightarrow{-3}3\xrightarrow{-1}2\xrightarrow{-1}1$$$.

Sample Inputs:
3
3
5
14

Sample Outputs:
3
3 2 1
4
5 4 2 1
6
14 12 6 3 2 1

Solution (Python):
def Ye():
    print('Yes')

def No():
    print('No')

def pl(li):
    for i in li:
        print(i, end=' ')

def solve():
    n = int(input())
    now = n
    cnt = 0
    acu = 0
    li = []
    bit = 1
    for i in range(1001):
        if n == 0:
            break
        while n % 2 == 0 and n:
            n //= 2
            bit *= 2
        if n == 0:
            break
        li.append(bit)
        n -= 1
    ans = [now]
    for i in li[:-1]:
        now -= i
        ans.append(now)
    bit //= 2
    while bit:
        ans.append(bit)
        bit //= 2
    print(len(ans))
    print(' '.join(list(map(str, ans))))
    return 0
TT = int(input())
while TT:
    solve()
    TT -= 1

Solution (Python):
def main():
    t = int(input())
    for _ in range(t):
        x = int(input())
        ans = []
        x_next = x & x - 1
        while x_next != 0:
            ans.append(x)
            x = x_next
            x_next = x & x - 1
        x_next = x >> 1
        while x_next != 0:
            ans.append(x)
            x = x_next
            x_next = x >> 1
        ans.append(x)
        print(len(ans))
        print(' '.join(map(str, ans)))
if __name__ == '__main__':
    main()

Solution (Python):
t = int(input())
for ti in range(t):
    x = int(input())
    chain = [x]
    start = 1
    while start < x:
        if x & start == start:
            x -= start
            chain.append(x)
        start <<= 1
    while x > 1:
        x >>= 1
        chain.append(x)
    print(len(chain))
    print(' '.join([str(i) for i in chain]))