← 返回题目列表

Codeforces · 1864/C

C. 除数链

中文机器翻译题面 查看原题

给你一个整数 $$$x$$$。您的任务是将 $$$x$$$ 减少到 $$$1$$$。

为此,您可以执行以下操作:

- 选择$$$x$$$的除数$$$d$$$,然后将$$$x$$$更改为$$$x-d$$$,即将$$$x$$$减少$$$d$$$。 (如果 $$$d$$$ 是一个正整数并且存在一个整数 $$$q$$$ 使得 $$$x = d \cdot q$$$,我们就说 $$$d$$$ 是 $$$x$$$ 的约数。)

还有一个附加限制:您不能选择 $$$d$$$ 的相同值两次以上。

例如,对于 $$$x=5$$$,以下方案无效,因为 $$$1$$$ 被选择两次以上:$$$5\xrightarrow{-1}4\xrightarrow{-1}3\xrightarrow{-1}2\xrightarrow{-1}1$$$。然而,以下方案是有效的方案:$$$5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1$$$。

输出任何方案,通过最多 $$$1000$$$ 操作将 $$$x$$$ 减少到 $$$1$$$。可以证明这样的方案总是存在的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$x$$$ ($$$2\le x \le 10^{9}$$$)。

输出

对于每个测试用例,输出两行。

第一行应包含一个整数 $$$k$$$ ($$$1 \le k \le 1001$$$)。

下一行应包含 $$$k$$$ 整数 $$$a_1,a_2,\ldots,a_k$$$,满足以下条件:

- $$$a_1=x$$$;
- $$$a_k=1$$$;
- 对于每个 $$$2 \le i \le k$$$,值 $$$(a_{i-1}-a_i)$$$ 是 $$$a_{i-1}$$$ 的除数。每个数字最多可以作为除数出现两次。

示例

输入 #1

3
3
5
14

输出 #1

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

注意

在第一个测试用例中,我们使用以下方案:$$$3\xrightarrow{-1}2\xrightarrow{-1}1$$$。

在第二个测试用例中,我们使用以下方案:$$$5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1$$$。

在第三个测试用例中,我们使用以下方案:$$$14\xrightarrow{-2}12\xrightarrow{-6}6\xrightarrow{-3}3\xrightarrow{-1}2\xrightarrow{-1}1$$$。