自动搬运

查看原文

来自洛谷，原作者为

	Naszt 数论，我的挚爱 | 看个人介绍请删除 "display: none;" 元素

搬运于2025-08-24 23:06:00，当前版本为作者最后更新于2024-11-14 23:06:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P11277 世界沉睡童话

我场切了？真的假的？飘了。
而且感觉思维和代码复杂度都比官方解答简单。

思路分析

step1 找突破口

我们先考虑极端情况

对于 $k=\binom{n}{2}=\frac{n(n-1)}{2}$:
容易想到构造 $\{1,1,1,\dots,1\}$。
两两相等即互相整除。

对于 $k=0$:
容易想到构造 $\{n,n+1,n+2,\dots,2n-1\}$。
这样最大也不会到两倍，即两两不整除。

按照类似的思路

对于 $k<n-1$:
构造 $\{n,\dots,n,n+1,\dots,n+1,\dots\}$。
这样形成 $x_1/x_2/\dots$ 个 $n/n+1/\dots$。
每 $x$ 个相同的数字之间互相整除，不同数字之间仍旧不整除，
即 $\sum \binom{x_i}{2}=k$。

我们想要某个 $k$ 的意义下构造一组 $x$ 使得 $\sum x_i$ 尽可能的小，
可以贪心的划分长度，使得前面的 $x$ 尽可能的大，
这样是最优的，如果把前面的 $x$ 减少，那么 $\sum x_i$ 不会更少。
按照这种方法，只用保证 $n\ge\sum x_i=$ A336640$(k)$。
即 $k<n-1$ 是一个充分条件使得贪心方法可做。

对于 $k=n-1$:
构造 $\{1,n,n+1,n+2,\dots,2n-2\}$。
$1$ 可以被其他的所有数整除。

step2 合并

我的解法就是把这两种情况合并。

若 $k\ge n-1$，我们令第一项为 $1$。
这样就要解决一个子问题：$k'\gets k-(n-1),n'\gets n-1$

再按照一样的方法添加 $1$ 解决这个子问题。
直到 $k<n-1$，上方贪心的方法即可解决。

代码实现

还算比较短的 c 风格代码：

long long n,k,t;
main(){
  scanf("%Ld%Ld",&n,&k);
  for(int i=n-1;i<=k&&t<n;k-=i--,t++)
    printf("1 ");
  for(int i=n;i<2*n;i++)
    for(int j=0;j<=k&&t<n;k-=j++,t++)
      printf("%d ",i);
}