Divisor Chain

题面翻译

给定一个整数 $x$，目标是在最多 $1000$ 次操作内把 $x$ 减到 $1$。

定义一个操作：选择一个 $x$ 的因数 $d$，把 $x$ 修改为 $x-d$。

同时还有一个额外的限制：相同的 $d$ 值不能选择超过 $2$ 次。

有 $t$ 组测试数据。

数据范围：$1\le t\le 10^3,2\le x\le 10^9$。

题目描述

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.

输入格式

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} $ ).

输出格式

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.

样例 #1

样例输入 #1

3
3
5
14

样例输出 #1

3
3 2 1
4
5 4 2 1
6
14 12 6 3 2 1

提示

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 $ .

lowbit可以找最右边的第一个1的值（1后面全部都是0），而这个值必然是这个二进制数的约数，所以每减掉这个约数，到下一个10000....就又是这个数的约数，再减掉，每次减掉的约数越来越大，所以必不同，如果只有一个1了，就是100000，就不能减了，一减就是0，所以这种情况就可以一直除2，直到1，整个过程不会有数字超过2次，最多两次

const int N = 3e5 + 10;
int a[N];

void solve()
{
    int n;
    cin >> n;
    deque<int > q;
    q.push_back(n);
    while(lowbit(n)!=n)
    {
        n -= lowbit(n);
        q.push_back(n);
    }
    while (n != 1)
    {
        n /= 2;
        q.push_back(n);
    }
    cout << q.size() << '\n';
    while (q.size())
    {
        cout << q.front() << " ";
        q.pop_front();
    }
    cout << '\n';
}