P11277 世界沉睡童话

ooliver 发布于 2 天前 26 次阅读 OI

P11277 世界沉睡童话

观察到一个性质，就是 $[n,2n)$ 中每个数相互无法整除。

又观察到 1 可以带来 $n-1$ 的贡献， $x$ 个相同的数可以带来 $\frac {x(x-1)}{2}$ 的贡献，

所以根据这个性质模拟即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+5;
int n,k;
signed main(){
	cin>>n>>k;
	int idx=n;
	while(k>=n-1&&n>0){
		k-=(--n);
		cout<<"1 ";
	}
	while(n>0){
		int x=(1+sqrt(1+8*k))/2;
		for(int i=1;i<=x;i++) cout<<idx<<" ";
		idx++;
		k-=x*(x-1)/2,n-=x;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e7+5;
int n,k;
signed main(){
	cin>>n>>k;
	int idx=n;
	while(k>=n-1&&n>0){
		k-=(--n);
		cout<<"1 ";
	}
	while(n>0){
		int x=(1+sqrt(1+8*k))/2;
		for(int i=1;i<=x;i++) cout<<idx<<" ";
		idx++;
		k-=x*(x-1)/2,n-=x;
	}
	return 0;
}