题解：P11277 世界沉睡童话

· · 题解

① k=0，这启发我们在 [1,2n-1] 中找到 n 个数，并且任意两个不能够构成倍数关系，思考易得选取 n,n+1......2n-1 共 n 个数。

② k=\frac{n(n-1)}{2}，显然这n个数应该为同一个数。

③ k\leq n-1，联想 k=0、k=\frac{n(n-1)}{2} 的情况，我们是否可以令 n 个数先取 n,n+1......2n-1，然后改变其中的某些数令其相等，来拼凑出符合要求的数对？答案是可以的，用数学归纳法：

任意 k=n-1 的情况，我们都可以令其中一个数变为 1，其余数之间仍保持没有倍数关系即可。接下来只需要讨论 k<n-1 的情况能否顺利构成。

当 n\le 4时，容易构造出合法数组。

假设 n=x，k<x-1 都成立，当 n=x+1，k<x-1 时，只需要令新增加的一个数与 n=x 时构成的数组间都没有倍数关系即可，由于n变大了，这样的数显然存在；而对于 n=x+1，k=x-1，我们先令其中的 3 个数相等，此时构成了 3 个合法数对，我们还剩 x-2 个数需要构 x-4 个数对，此时一定在不借助1的情况下可以完成。（当然这里的构造方式有很多种，也可以用更多的相同的数，一次性构造更多的合法数对。）

综上，得证。

④最后讨论一般情况，根据③的结论，我们可以每次先令其中的一个数变成 1 ，则问题会转化为 n=n-1，k=k-(n-1) 的问题，如此递归下去，直到 k\le n-1 为止，问题得到解决。

#include<bits/stdc++.h>
using namespace std;
int re(){
    int num=0,fl=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') fl=-1;ch=getchar();}
    while(isdigit(ch)){num=num*10+ch-'0';ch=getchar();}
    return num*fl;
}
const int N=3e5+100;
int n,a[N],b=1;
long long k;
int main(){
    cin>>n>>k;
    if(k==0){
        for(int i=n;i<=2*n-1;++i)   cout<<i<<" ";
    }
    else{
        int nn=n;
        while(nn&&k>=nn-1){
            a[nn--]=1;k-=nn; 
        }
        while(nn>=4&&k>=3){
            a[nn]=a[nn-1]=a[nn-2]=2*n-b;
            ++b,k-=3,nn-=3;     
        }
        if(k==2)    a[nn]=a[nn-1]=2*n-b,++b,nn-=2,--k;
        if(k==1)    a[nn]=a[nn-1]=2*n-b,++b,nn-=2,--k;
        while(nn>0) a[nn]=2*n-b,++b,--nn;
        for(int i=1;i<=n;++i)   cout<<a[i]<<" ";
    }
    return 0;
}