题解 ARC115C【ℕ Coloring】

显然 \(A_1,A_2,A_4,A_8,\cdots\) 必须互不相同，因此最大的数一定不小于 \(\lfloor\log_2n\rfloor+1\)，猜想可以取到 \(\lfloor\log_2n\rfloor+1\)。

构造 \(A_i=\lfloor\log_2i\rfloor+1\)，则对于任意 \(A_i=A_j\) 都有 \(2i > j\)，不存在倍数关系。

时间复杂度 \(\Theta(n)\)。

// Problem: C - ℕ Coloring
// Contest: AtCoder - AtCoder Regular Contest 115
// URL: https://atcoder.jp/contests/arc115/tasks/arc115_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

int main() {
	int n;
	scanf("%d", &n);
	for(int L = 1, R, u = 1; L <= n; L = R + 1, u++) {
		R = 2 * L - 1;
		chkmin(R, n);
		rep(i, L, R) printf("%d%c", u, " \n"[i==n]);
	}
	return 0;
}