309573: CF1701B. Permutation

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Permutation

题意翻译

给定 $n$,要求构造一个 $n$ 的排列 $a$,使满足 $a_{i-1} \cdot d=a_i$ 的 $i$ 个数尽可能多($d$ 可以任选大于 $1$ 的正整数),输出这个排列以及你选择的 $d$

题目描述

Recall that a permutation of length $ n $ is an array where each element from $ 1 $ to $ n $ occurs exactly once. For a fixed positive integer $ d $ , let's define the cost of the permutation $ p $ of length $ n $ as the number of indices $ i $ $ (1 \le i < n) $ such that $ p_i \cdot d = p_{i + 1} $ . For example, if $ d = 3 $ and $ p = [5, 2, 6, 7, 1, 3, 4] $ , then the cost of such a permutation is $ 2 $ , because $ p_2 \cdot 3 = p_3 $ and $ p_5 \cdot 3 = p_6 $ . Your task is the following one: for a given value $ n $ , find the permutation of length $ n $ and the value $ d $ with maximum possible cost (over all ways to choose the permutation and $ d $ ). If there are multiple answers, then print any of them.

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases. The single line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ). The sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式


For each test case, print the value $ d $ in the first line, and $ n $ integers in the second line — the permutation itself. If there are multiple answers, then print any of them.

输入输出样例

输入样例 #1

2
2
3

输出样例 #1

2
1 2
3
2 1 3

Input

题意翻译

给定 $n$,要求构造一个 $n$ 的排列 $a$,使满足 $a_{i-1} \cdot d=a_i$ 的 $i$ 个数尽可能多($d$ 可以任选大于 $1$ 的正整数),输出这个排列以及你选择的 $d$

Output

题目大意:
给定整数n,构造一个n的排列a,使得满足$a_{i-1} \cdot d = a_i$的i个数尽可能多(d为任意大于1的正整数),输出这个排列以及你选择的d。

输入输出数据格式:
输入格式:
第一行包含一个整数t(1≤t≤500)——测试用例的数量。
每个测试用例的单行包含一个整数n(2≤n≤2×10^5)。
所有测试用例的n之和不超过2×10^5。

输出格式:
对于每个测试用例,第一行输出d的值,第二行输出n个整数——排列本身。如果有多个答案,则输出其中任意一个。题目大意: 给定整数n,构造一个n的排列a,使得满足$a_{i-1} \cdot d = a_i$的i个数尽可能多(d为任意大于1的正整数),输出这个排列以及你选择的d。 输入输出数据格式: 输入格式: 第一行包含一个整数t(1≤t≤500)——测试用例的数量。 每个测试用例的单行包含一个整数n(2≤n≤2×10^5)。 所有测试用例的n之和不超过2×10^5。 输出格式: 对于每个测试用例,第一行输出d的值,第二行输出n个整数——排列本身。如果有多个答案,则输出其中任意一个。

加入题单

上一题 下一题 算法标签: