A16701 | $Distinct GCDs (Easy Version)$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

这是该题的简单版本。不同版本的区别在于本版本中 $n \leq 700$。你只有在解决了所有版本的问题后才能进行 hack。 传说中，高斯小时候在课堂上，老师让同学们计算 $1$ 到 $100$ 的整数和，想以此让他们安静一阵。但小高斯很快就写出了 $\text{sum} = \frac{n(n+1)}{2}$ 的公式，瞬间得出了答案。几个世纪后，高斯在你的梦中出现，并带来了一项艰巨的任务…… 给定一个正整数 $n$，请你构造一个长度为 $n$ 的整数序列 $[a_1, a_2, \ldots, a_n]$，使得对于所有 $1 \leq i \leq n$ 有 $1 \leq a_i \leq 10^{18}$，并且相邻任意两个元素的最大公约数均不相同。形式化地说， 对于 $1 \leq i < j < n$，都有 $\gcd(a_i, a_{i+1}) \neq \gcd(a_j, a_{j+1})$。 此外，要求 $a$ 中不同元素的数量尽可能少。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 200$），表示测试数据的组数。 接下来每组测试数据包含一行，包含一个整数 $n$（$2 \leq n \leq 700$），表示需构造的序列长度。

对于每组测试数据，输出 $n$ 个用空格分隔的正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^{18}$），使得它们满足题目的要求。若有多组满足条件的解，输出任意一组均可。 可以证明，在题目给定的约束范围内，总是存在解。

输入 #1

输出 #1

2 2
1 4 4 6 6
4 4 6 6 9 9 4

C++ 编辑器

输入

输出