夕阳西下几时回

Luogu
IDLGP9345
Time1000ms
Memory128MB
DifficultyP4
贪心洛谷原创Special JudgeO2优化构造洛谷月赛
夕阳可以被视作由 $n$ 种不同颜色组成的一副图,其中第 $i$ 种的颜色为 $a_i$,满足 $a$ 是长度为 $n$ 的排列。 定义一个排列的乡愁度为: + 对于所有 $1\le i\le n$,记 $b_i=\gcd(a_i,a_{i+1})$。特别地,我们认为 $a_{n+1}=a_1$。 + 排列 $a$ 的乡愁度为序列 $b$ 中**不同**元素的个数。 求是否有一个长度为 $n$,乡愁度为 $k$ 的排列 $p$。若有解,请输出任意一个排列。 ## Input **本题有多组测试数据。** 第一行一个正整数 $T$,表示测试数据组数。 对于每组测试数据,一行两个整数 $n,k$。 ## Output 对于每组测试数据: - 如果不存在这样的排列,输出一行一个字符串 `No`; - 否则,输出一行一个字符串 `Yes`,然后输出一行 $n$ 个正整数 $p_1,p_2,\dots,p_n$,表示你找到的排列。 校验器忽略字符串大小写,例如,`YES`,`yEs`,`yes` 都会被视作答案存在。 [samples] ## Background 随着夕阳从山间落下,最后一丝余晖逐渐暗淡;美丽的晚霞,终究还是化作一片黑夜。在这番景象中,一阵又一阵的乡愁涌上心头;远离家乡的游子,就算不是病死他乡,又何时能回还? ## Note **【提示】** 一个长度为 $n$ 的排列是一个满足 $1$ 到 $n$ 中的所有正整数恰好出现 $1$ 次的数组。例如,$[3,1,2]$ 是一个长度为 $3$ 的排列,而 $[5,5,1,2,3]$ 不是一个排列。 **【样例 1 解释】** - 对于第一组数据,$b=[1,1,1,1,1,1,1]$,故 $p$ 的乡愁度为 $1$。 - 对于第二组数据,可以证明不存在这样的序列。 - 对于第三组数据,$b=[1,1,3,3,1,1,2,1,5,2,1]$,包含 $4$ 个不同的元素 — $1,2,3$ 和 $5$,故 $p$ 的乡愁度为 $4$。 **【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1(4 points):$n\le 9$,$\sum n\le 100$。 - Subtask 2(5 points):$k=1$。 - Subtask 3(13 points):$\sum n\le 200$。 - Subtask 4(30 points):对于所有测试数据,保证有解。 - Subtask 5(48 points):无特殊限制。 对于 $100\%$ 的数据,$1\le T\le 10^5$,$3\le n\le 3\times 10^5$,$1\le k\le n$,$\sum n \le 6\times 10^5$。
Samples
Input #1
3
7 1
6 5
11 4
Output #1
Yes
1 2 3 4 5 6 7
No
Yes
1 11 9 3 6 7 8 2 5 10 4
API Response (JSON)
{
  "problem": {
    "name": "夕阳西下几时回",
    "description": {
      "content": "夕阳可以被视作由 $n$ 种不同颜色组成的一副图,其中第 $i$ 种的颜色为 $a_i$,满足 $a$ 是长度为 $n$ 的排列。 定义一个排列的乡愁度为: + 对于所有 $1\\le i\\le n$,记 $b_i=\\gcd(a_i,a_{i+1})$。特别地,我们认为 $a_{n+1}=a_1$。 + 排列 $a$ 的乡愁度为序列 $b$ 中**不同**元素的个数。 求是否有一个长度为 $n",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9345"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "夕阳可以被视作由 $n$ 种不同颜色组成的一副图,其中第 $i$ 种的颜色为 $a_i$,满足 $a$ 是长度为 $n$ 的排列。\n\n定义一个排列的乡愁度为:\n\n+ 对于所有 $1\\le i\\le n$,记 $b_i=\\gcd(a_i,a_{i+1})$。特别地,我们认为 $a_{n+1}=a_1$。\n+ 排列 $a$ 的乡愁度为序列 $b$ 中**不同**元素的个数。\n\n求是否有一个长度为 $n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments