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 解决这个子问题。
直到 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);
}