D. The 67th OEIS Problem

    传统题 2000ms 256MiB

The 67th OEIS Problem

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Macaque 是一个糟糕的出题人。某天他决定在 OEIS∗^{\text{∗}} 上搜索有趣的数列,以便为他注定失败的泛哺乳动物信息学奥林匹克(PMOI)出题工作寻找灵感。令他高兴的是,他找到了一个,并觉得让你——他忠实的测试员——来解决它会很有趣:

构造一个包含 nn 个整数的序列 aa,使得对于所有 1≤i≤n−11 \leq i \leq n - 1,gcd⁡(ai,ai+1)\operatorname{gcd}(a_i, a_{i+1}) †^{\text{†}} 的值互不相同。保证至少存在一个满足条件的序列 aa。

∗^{\text{∗}}OEIS 指整数数列在线百科全书,是数学极客、过于敏锐的测试员和不够严谨的协调员们最喜爱的网站。

†^{\text{†}}gcd⁡(x,y)\operatorname{gcd}(x,y) 表示整数 xx 和 yy 的最大公约数。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1001 \le t \le 100)。接下来是各个测试用例的描述。

以下 tt 行每行包含一个整数 nn(2≤n≤1042 \leq n \leq 10^4)——即所需构造序列的长度。

保证所有测试用例的 nn 之和不超过 10410^4。

输出格式

对于每个查询,输出你的答案——一个由 nn 个空格分隔的整数组成的序列 aa(1≤ai≤10181 \le a_i \le 10^{18})。

样例

2
3
5
1 6 2
134 67 69 207 414

说明

在第一个测试用例中,序列 [1,6,2][1, 6, 2] 是一个可能的答案。这是因为 gcd⁡(1,6)\gcd(1, 6) 不等于 gcd⁡(6,2)\gcd(6, 2)。

在第二个测试用例中,序列 [134,67,69,207,414][134, 67, 69, 207, 414] 是一个可能的答案。这是因为对于 11 到 n−1n-1 之间的所有 ii,gcd⁡(ai,ai+1)\gcd(a_i, a_{i+1}) 的值互不相同。具体来说,它们分别是 6767、11、6969 和 207207。

来源

导入自 Codeforces — Codeforces Round 1090 (Div. 4)。

Codeforces Round 1090 (Div. 4)

未参加
状态
已结束
规则
XCPC
题目
7
开始于
2026-11-11 15:00
结束于
2026-11-11 17:30
持续时间
2.5 小时
主持人
参赛人数
14