题目传送门
众所周知一篇题解需要一个头图。
题目大意
构造一个仅由 \(1\sim n\) 组成的长度为 \(n\) 的排列，使得相邻两项的 \(\gcd\) 有 \(k\) 种不同的数（乡愁度）。
解题思路
前置知识：如果两个数有倍数关系，那么这两个数的 \(\gcd\) 是那个较小的数，即 \(\gcd(x,kx)=x\)（\(k\)、\(x\) 均为整数）。
首先考虑最大的 \(\gcd\) 的种类（乡愁度）有多少种：
一个每相邻两项之间都有倍数关系的长度为 \(i\) 的排列它的乡愁度贡献为 \(i-1\)（每相邻两项之间都是一个新的 \(\gcd\)），那么我们考虑将 \(1\sim n\) 的排列分成若干个这种排列，设这个倍数关系为 \(k\) 倍，则可知从 \(1\) 开始排列的那个排列最长，其他排列成比例减少，这个最长排列为：
一直到 \(k^i>n\) 时排列终止，排列长度为 \(\left \lfloor \log _k n \right \rfloor +1\)。
由此可知当且仅当 \(k=2\) 时排列最长，此时 \(1\sim n\) 分成的排列也最少，答案也就会越大。
此时从小到大每次选取没被排列过的数为首每次 \(\times 2\)，得到的排列即为乡愁度最大的排列，如果这个排列的乡愁度为 \(ans\)，那么当 \(k>ans\) 时无解。
考虑 \(k<ans\) 的情况：
当按照如上方式从 \(1\sim n\) 中取出排列并记录此时答案，当此时答案达到 \(k\) 时把剩下的数从小到大排列，每两个数之间的 \(\gcd\) 一定为 \(1\)，证明如下：
-
当取第一个（首项为 \(1\)，公比为 \(2\)）排列之前，剩余的数均相邻，由 \(\gcd(i,i+1)=1\) 得，剩下的数相邻两项的 \(\gcd\) 一定为 \(1\)；
-
当取第一个（首项为 \(1\)，公比为 \(2\)）排列之后，剩余的数均为奇数，剩余的相邻两项之间差值为若干个 \(2\)，且后一个数不会是前一个数的倍数（前一个数最小为 \(3\)，它和它的最近倍数 \(9\) 之间存在质数，而质数只能当排列的第一个数，此时前一个数已经被取走，不会是剩余的数），则相邻两项的 \(\gcd\) 也是 \(1\)。
则将剩下的数从小到大排列输出不会对答案产生影响，所以当答案达到 \(k\) 时结束并将剩余的数输出就能保证答案为 \(k\)。
AC Code
防止作弊只放主函数：
signed main()
{T=re();while(T--){n=re(),k=re(),ans=0;for(int i=1;i<=n;i++)//初始化好习惯 vis[i]=0;//vis数组存这个数在没在排列中出现过 for(int i=1;i<=n;i++)//先求最大ans {if(!vis[i]){for(int temp=i;temp<=n;temp*=2)vis[temp]=1,ans+=(temp!=i);}}if(k>ans)//判断无解情况 puts("No");else{ans=0;for(int i=1;i<=n;i++)//初始化好习惯*2 vis[i]=0;puts("Yes");for(int i=1;i<=n;i++){if(!vis[i]){if(ans==k)//按照那个方法排列直到ans=k break;for(int temp=i;temp<=n;temp*=2){wr(temp),putchar(' '),vis[temp]=1,ans+=(temp!=i);if(ans==k)break;}}}for(int i=1;i<=n;i++)//将剩下的数从小到大输出 if(!vis[i])wr(i),putchar(' ');putchar('\n');}}return 0;
}