Logo Wy Online Judge

WyOJ

#767. 宝库密码

题目背景

在数字王国中,国王需要为宝库设置一系列密码。然而王国的古老魔法有一个禁忌:任何一段连续密码的数字之和,都绝对不能是神秘数字 $k$ 的倍数,否则警报就会响起。

题目描述

你需要构造一个严格递增的正整数序列 $a_1 < a_2 < \dots < a_n$,使得对任意 $1 \le l \le r \le n$,都有

$$k \nmid \sum_{i=l}^{r} a_i$$

即任意一个长度至少为 $1$ 的连续子段之和都不是 $k$ 的倍数。

在所有满足条件的序列中,求出字典序最小的一个(字典序比较:自左向右逐位比较,先出现较小元素者更小)。若不存在任何满足条件的序列,输出 $-1$。

本题有多组测试数据。

输入格式

第一行一个整数 $T$,表示测试数据组数。

接下来 $T$ 行,每行两个整数 $n, k$,表示一组询问。

输出格式

对于每组测试数据:

  • 若存在满足条件的序列,输出一行 $n$ 个空格分隔的整数,表示字典序最小的序列;
  • 否则输出一行 $-1$。

注:由于未知原因,请不要输出行末空格。

样例

样例 1 输入

3
3 3
2 3
4 5

样例 1 输出

-1
1 4
1 2 4 7

样例 1 说明

第二组:序列 $[1, 4]$ 的连续段和为 $1, 4, 5$,均不是 $3$ 的倍数,且为字典序最小。

数据范围与提示

测试点编号 特殊性质 分值
$1 \sim 2$ $n, k \le 8$ 且 $T \le 10$ $20$
$3 \sim 4$ 所有数据满足 $n \ge k$ $20$
$5 \sim 7$ $T \le 20$ 且 $k \le 2000$ $30$
$8 \sim 10$ 无特殊限制 $30$

对于全部数据:$1 \le T \le 10^5$,$1 \le n, k \le 2 \times 10^5$,且所有测试数据的 $k$ 之和不超过 $5 \times 10^5$。

时间限制:1 秒;内存限制:512 MB。

题目信息
  • 难度 UKE
  • 控制组 默认组
  • 时间限制 1 s
  • 空间限制 512 MB
  • 数据大小 1.364 MB
提交统计
  • 提交数 72
  • 通过数 23
  • 通过率 31.9%