309909: CF1758C. Almost All Multiples

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

Description

Almost All Multiples

题意翻译

给定 $n$ 和 $x$,求一个 $1$ 到 $n$ 的字典序最小的排列 $\{ p_n \}$,满足 $p_1 = x, \ p_n = 1$,且对所有 $i \in [1, n)$ 有 $i \mid p_i$。

题目描述

Given two integers $ n $ and $ x $ , a permutation $ ^{\dagger} $ $ p $ of length $ n $ is called funny if $ p_i $ is a multiple of $ i $ for all $ 1 \leq i \leq n - 1 $ , $ p_n = 1 $ , and $ p_1 = x $ . Find the lexicographically minimal $ ^{\ddagger} $ funny permutation, or report that no such permutation exists. $ ^{\dagger} $ A permutation of length $ n $ is an array consisting of each of the integers from $ 1 $ to $ n $ exactly once. $ ^{\ddagger} $ Let $ a $ and $ b $ be permutations of length $ n $ . Then $ a $ is lexicographically smaller than $ b $ if in the first position $ i $ where $ a $ and $ b $ differ, $ a_i < b_i $ . A permutation is lexicographically minimal if it is lexicographically smaller than all other permutations.

输入输出格式

输入格式


The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows. The only line of each test case contains two integers $ n $ and $ x $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ; $ 1 < x \leq n $ ). The sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式


For each test case, if the answer exists, output $ n $ distinct integers $ p_1, p_2, \dots, p_n $ ( $ 1 \leq p_i \leq n $ ) — the lexicographically minimal funny permutation $ p $ . Otherwise, output $ -1 $ .

输入输出样例

输入样例 #1

3
3 3
4 2
5 4

输出样例 #1

3 2 1 
2 4 3 1 
-1

说明

In the first test case, the permutation $ [3,2,1] $ satisfies all the conditions: $ p_1=3 $ , $ p_3=1 $ , and: - $ p_1=3 $ is a multiple of $ 1 $ . - $ p_2=2 $ is a multiple of $ 2 $ . In the second test case, the permutation $ [2,4,3,1] $ satisfies all the conditions: $ p_1=2 $ , $ p_4=1 $ , and: - $ p_1=2 $ is a multiple of $ 1 $ . - $ p_2=4 $ is a multiple of $ 2 $ . - $ p_3=3 $ is a multiple of $ 3 $ . We can show that these permutations are lexicographically minimal. No such permutations exist in the third test case.

Input

题意翻译

给定 $n$ 和 $x$,求一个 $1$ 到 $n$ 的字典序最小的排列 $\{ p_n \}$,满足 $p_1 = x, \ p_n = 1$,且对所有 $i \in [1, n)$ 有 $i \mid p_i$。

Output

**题意翻译**

给定 $n$ 和 $x$,求一个 $1$ 到 $n$ 的字典序最小的排列 $\{ p_n \}$,满足 $p_1 = x, \ p_n = 1$,且对所有 $i \in [1, n)$ 有 $i \mid p_i$。

**题目描述**

给定两个整数 $n$ 和 $x$,一个长度为 $n$ 的排列 $p$ 被称为有趣的,如果对于所有 $1 \leq i \leq n - 1$,$p_i$ 是 $i$ 的倍数,$p_n = 1$,且 $p_1 = x$。

找出字典序最小的有趣排列,或者报告没有这样的排列存在。

**输入输出格式**

**输入格式**

输入由多个测试案例组成。第一行包含一个整数 $t$($1 \leq t \leq 10^4$)——测试案例的数量。测试案例的描述如下。

每个测试案例只有一行,包含两个整数 $n$ 和 $x$($2 \leq n \leq 2 \cdot 10^5$;$1 < x \leq n$)。

所有测试案例中 $n$ 的总和不超过 $2 \cdot 10^5$。

**输出格式**

对于每个测试案例,如果答案存在,输出 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$($1 \leq p_i \leq n$)——字典序最小的有趣排列 $p$。否则,输出 $-1$。

**输入输出样例**

**输入样例 #1**

```
3
3 3
4 2
5 4
```

**输出样例 #1**

```
3 2 1
2 4 3 1
-1
```

**说明**

在第一个测试案例中,排列 $[3,2,1]$ 满足所有条件:$p_1=3$,$p_3=1$,且:

- $p_1=3$ 是 $1$ 的倍数。
- $p_2=2$ 是 $2$ 的倍数。

在第二个测试案例中,排列 $[2,4,3,1]$ 满足所有条件:$p_1=2$,$p_4=1$,且:

- $p_1=2$ 是 $1$ 的倍数。
- $p_2=4$ 是 $2$ 的倍数。
- $p_3=3$ 是 $3$ 的倍数。

我们可以证明这些排列是字典序最小的。

在第三个测试案例中没有这样的排列存在。**题意翻译** 给定 $n$ 和 $x$,求一个 $1$ 到 $n$ 的字典序最小的排列 $\{ p_n \}$,满足 $p_1 = x, \ p_n = 1$,且对所有 $i \in [1, n)$ 有 $i \mid p_i$。 **题目描述** 给定两个整数 $n$ 和 $x$,一个长度为 $n$ 的排列 $p$ 被称为有趣的,如果对于所有 $1 \leq i \leq n - 1$,$p_i$ 是 $i$ 的倍数,$p_n = 1$,且 $p_1 = x$。 找出字典序最小的有趣排列,或者报告没有这样的排列存在。 **输入输出格式** **输入格式** 输入由多个测试案例组成。第一行包含一个整数 $t$($1 \leq t \leq 10^4$)——测试案例的数量。测试案例的描述如下。 每个测试案例只有一行,包含两个整数 $n$ 和 $x$($2 \leq n \leq 2 \cdot 10^5$;$1 < x \leq n$)。 所有测试案例中 $n$ 的总和不超过 $2 \cdot 10^5$。 **输出格式** 对于每个测试案例,如果答案存在,输出 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$($1 \leq p_i \leq n$)——字典序最小的有趣排列 $p$。否则,输出 $-1$。 **输入输出样例** **输入样例 #1** ``` 3 3 3 4 2 5 4 ``` **输出样例 #1** ``` 3 2 1 2 4 3 1 -1 ``` **说明** 在第一个测试案例中,排列 $[3,2,1]$ 满足所有条件:$p_1=3$,$p_3=1$,且: - $p_1=3$ 是 $1$ 的倍数。 - $p_2=2$ 是 $2$ 的倍数。 在第二个测试案例中,排列 $[2,4,3,1]$ 满足所有条件:$p_1=2$,$p_4=1$,且: - $p_1=2$ 是 $1$ 的倍数。 - $p_2=4$ 是 $2$ 的倍数。 - $p_3=3$ 是 $3$ 的倍数。 我们可以证明这些排列是字典序最小的。 在第三个测试案例中没有这样的排列存在。

加入题单

上一题 下一题 算法标签: