CF1844B.Permutations & Primes
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given a positive integer n .
In this problem, the MEX of a collection of integers c1,c2,…,ck is defined as the smallest positive integer x which does not occur in the collection c .
The primality of an array a1,…,an is defined as the number of pairs (l,r) such that 1≤l≤r≤n and MEX(al,…,ar) is a prime number.
Find any permutation of 1,2,…,n with the maximum possible primality among all permutations of 1,2,…,n .
Note:
- A prime number is a number greater than or equal to 2 that is not divisible by any positive integer except 1 and itself. For example, 2,5,13 are prime numbers, but 1 and 6 are not prime numbers.
- A permutation of 1,2,…,n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation ( 2 appears twice in the array), and [1,3,4] is also not a permutation ( n=3 but there is 4 in the array).
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤104 ). The description of the test cases follows.
The only line of each test case contains a single integer n ( 1≤n≤2⋅105 ).
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
输出格式
For each test case, output n integers: a permutation of 1,2,…,n that achieves the maximum possible primality.
If there are multiple solutions, print any of them.
输入输出样例
输入#1
3 2 1 5
输出#1
2 1 1 5 2 1 4 3
说明/提示
In the first test case, there are 3 pairs (l,r) with 1≤l≤r≤2 , out of which 2 have a prime MEX(al,…,ar) :
- (l,r)=(1,1) : MEX(2)=1 , which is not prime.
- (l,r)=(1,2) : MEX(2,1)=3 , which is prime.
- (l,r)=(2,2) : MEX(1)=2 , which is prime.
Therefore, the primality is 2 .In the second test case, MEX(1)=2 is prime, so the primality is 1 .
In the third test case, the maximum possible primality is 8 .