A16701. Distinct GCDs (Easy Version)
编程题
省选/NOI-
知识点
题目描述
这是该题的简单版本。不同版本的区别在于本版本中 $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$ 中不同元素的数量尽可能少。
传说中，高斯小时候在课堂上，老师让同学们计算 $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$（$2 \leq n \leq 700$），表示需构造的序列长度。
输出格式
对于每组测试数据，输出 $n$ 个用空格分隔的正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^{18}$），使得它们满足题目的要求。若有多组满足条件的解，输出任意一组均可。
可以证明，在题目给定的约束范围内，总是存在解。
可以证明，在题目给定的约束范围内，总是存在解。
输入输出样例
输入 #1
3 2 5 7
输出 #1
2 2 1 4 4 6 6 4 4 6 6 9 9 4
说明/提示
对于第二组样例，相邻元素的最大公约数为 $[\gcd(1, 4), \gcd(4, 4), \gcd(4, 6), \gcd(6, 6)] = [1, 4, 2, 6]$，均不相同。
对于第三组样例，相邻元素的最大公约数为 $[\gcd(4, 4), \gcd(4, 6), \gcd(6, 6), \gcd(6, 9), \gcd(9, 9), \gcd(9, 4)] = [4, 2, 6, 3, 9, 1]$，均不相同。
对于每组测试数据，都可以证明，无法使用更少的不同元素得到所有相邻最大公约数均不同的序列。
对于第三组样例，相邻元素的最大公约数为 $[\gcd(4, 4), \gcd(4, 6), \gcd(6, 6), \gcd(6, 9), \gcd(9, 9), \gcd(9, 4)] = [4, 2, 6, 3, 9, 1]$，均不相同。
对于每组测试数据，都可以证明，无法使用更少的不同元素得到所有相邻最大公约数均不同的序列。