P11277 世界沉睡童话

k=0

答案就是 n,n+1,n+2,\dots,2n-2,2n-1。

这一些数显然满足条件。

因为 2\times n\ge 2n-1，头一个数的两倍大于最后一个数，所以不会有倍数关系。

k\le n-1

当前 k 比较小。考虑一些分组的做法。

把 a 分成若干组，组组之间没有倍数关系，组内的数全部相等。

设每一个组的数量为 p_i，一共有 m 个组。

那么当前的答案就是：

\sum\limits_{i=1}^{m}\binom{p_i}{2}

每一个数可以取 k=0 时候的数，根据上面的描述，组之间肯定没有倍数关系。

每一次二分出当前的最大的 p_i，使得 \binom{p_i}{2}\le k，然后填入 p_i 个数。

k\le \frac{n(n-1)}{2}

打表发现，每一个 1 有非常大的用处。

因为 a 的顺序无关紧要，设前面 x 个数都是 1。

每一个 1 都能跟后面的所有数产生贡献，所以当前的贡献为：

(n-1)+(n-2)+\cdots+(n-x+1)+(n-x)\\ =\frac{(2n-1-x)x}{2}

后面的 n-x 个数产生 k-\frac{(2n-1-x)x}{2} 的贡献就可以了。

如果你取到当前最大的 x，会发现，k-\frac{(2n-1-x)x}{2}\le (n-x)-2。

也就是，k'\le n'-2。再拼上 k\le n-1 的做法就对了。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2.5e5+5;
int n,k;
inline int S(int x){
    return (2*n-1-x)*x/2;
}
inline int C2(int x){return x*(x-1)/2;}
int ans[MAXN];
inline void solve(){
    int x=0;
    for(int i=0;i<=n;i++){
        if(S(i)<=k&&S(i+1)>k){
            k-=S(i);x=i;break;
        }
    }
    for(int i=1;i<=x;i++)ans[i]=1;
    int cnt=2*n-1,lin=x+1;
    while(k>0){
        int l=1,r=n,del=1;
        while(l<=r){
            int mid=l+r>>1;
            if(C2(mid)<=k){
                l=mid+1,del=mid;
            }else r=mid-1;
        }
        k-=C2(del);
        for(int i=lin;i<=lin+del-1;i++)ans[i]=cnt;
        lin+=del;cnt--;
    }
    if(lin<=n){
        for(int i=lin;i<=n;i++)ans[i]=cnt,cnt--;
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" ";cout<<"\n";
}
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>k;solve();
}