← 返回题目列表

Codeforces · 715/A

A. 加号和平方根

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

编码员 ZS 正在玩游戏。屏幕上显示一个数字,并有两个按钮:“+”(加号)和“$$\sqrt{}$$”(平方根)。最初,数字 2 显示在屏幕上。游戏中有 n + 1 个关卡,编码器 ZS 从第 1 关开始。

当编码器 ZS 处于 k 级时,他可以:

1. 按“ + ”按钮。这会将屏幕上的数字恰好增加 k。所以,如果屏幕上的数字是x,它就变成x + k。
2. 按“$$\sqrt{}$$”按钮。设屏幕上的数字为x。按下此按钮后,数字变为$$\sqrt{x}$$。之后,编码员ZS升级了,所以他当前的等级变成了k + 1。只有当x是完全平方数时才能按下该按钮,即对于某个正整数m,x = m2。

另外,每次移动后,如果 ZS 编码器处于 k 级,并且屏幕上的数字为 m,则 m 必须是 k 的倍数。请注意,仅在执行按压后才会检查此条件。例如,如果ZS编码员是4级,当前数字是100,那么他按下'$$\sqrt{}$$'按钮,数字变成10。注意,此时10不能被4整除,但是这个按键仍然有效,因为之后ZS编码员是5级,10可以被5整除。

ZS 编码员需要您的帮助来通关游戏 - 他想要达到 n + 1 级。换句话说,他需要按“$$\sqrt{}$$”按钮 n 次。帮助他确定在每个级别按“$$\sqrt{}$$”按钮之前应按“+”按钮的次数。

请注意,ZS 编码员想要找到任何允许他达到级别 n + 1 的按下序列,但不一定是最小化按下次数的序列。

输入

输入的第一行也是唯一一行包含单个整数 n (1 ≤ n ≤ 100 000),表示编码器希望达到级别 n + 1。

输出

打印 n 个非负整数,每行一个。其中第 i 个应该等于编码器在第 i 级按“$$\sqrt{}$$”按钮之前需要按“+”按钮的次数。

输出中的每个数字不应超过 1018。但是,屏幕上的数字可以大于 1018。

保证至少存在一个解。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3

输出 #1

14
16
46

输入 #2

2

输出 #2

999999999999999998
44500000000

输入 #3

4

输出 #3

2
17
46
97

注意

在第一个示例案例中:

在第一关,编码员 ZS 按了“+”按钮 14 次(屏幕上的数字最初为 2),因此数字变为 2 + 14·1 = 16。然后,编码员 ZS 按了“$$\sqrt{}$$”按钮,数字变为 $$\sqrt{16} = 4$$。

之后,在第二关,ZS按了“+”按钮16次,因此数字变为4 + 16·2 = 36。然后,ZS按了“$$\sqrt{}$$”按钮,升级并将数字更改为$$\sqrt{36} = 6$$。

之后,在第三关,ZS按了“+”按钮46次,因此数字变为6 + 46·3 = 144。然后,ZS按了“$$\sqrt{}$$”按钮,升级并将数字更改为$$\sqrt{144} = 12$$。

请注意,12 确实可以被 4 整除,因此 ZS 编码器可以达到级别 4。

另外,请注意,在升级之前在第三级按“+”按钮 10 次不起作用,因为数字变为 6 + 10·3 = 36,而当按下“$$\sqrt{}$$”按钮时,数字变为 $$\sqrt{36} = 6$$,并且 ZS 编码器处于级别 4。但是,6 不能被整除现在是 4,所以这不是一个有效的解决方案。

在第二个示例案例中:

第一关,编码员ZS按了“+”键999999999999999998次(屏幕上的数字最初是2),所以数字变成了2 + 999999999999999998·1 = 1018。然后,编码员ZS按了'$$\sqrt{}$$'按钮,数字变为$$\sqrt{10^{18}} = 10^9$$。

之后,在第二关,ZS按了“+”按钮44500000000次,所以数字变成109 + 44500000000·2 = 9·1010。然后,ZS按下‘$$\sqrt{}$$’按钮,升级并将数字变为$$\sqrt { 9 \cdot 1 0 ^ { 1 0 } } = 3 0 0 0 0 0$$。

注意300000是3的倍数,所以ZS编码器可以达到3级。