Codeforces 922F Divisibility （构造 + 数论）

题目链接 Divisibility

题意给定$n$和$k$，构造一个集合$\left\{1, 2, 3, ..., n \right\}$的子集，使得在这个集合中恰好有$k$对正整数$(x, y)$, $x < y$

　　满足$x$是$y$的约数。

选定$1$和$2$，

首先把满足 $x > [\frac{n}{2}]\ $的质数$x$留出来，

然后把满足 $ [\frac{n}{3}]\ < x <= [\frac{n}{2}]\ $的质数，以及他们的两倍留出来，

留出来的这些数先不选，从$3$开始一个个开始选。

接近$k$的时候开始选刚刚留出来的那些数,

先选满足 $x > [\frac{n}{2}]\ $的质数，满足题意的正整数对数加$1$，

再选满足 $ [\frac{n}{3}]\ < x <= [\frac{n}{2}]\ $的质数的两倍，满足题意的正整数对数加$2$，

最后选满足 $ [\frac{n}{3}]\ < x <= [\frac{n}{2}]\ $的质数，满足题意的正整数对数加$2$。

选完这些如果还是到不了$k$，那么无解。

本来想着$n$小的时候直接特判（$O(2^{n})$暴力）的，但是把特判去掉交上去居然也通过了……

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 3e5 + 10;

int a[N], b[N], c[N], f[N];

int n, k, num1 = 0, num2 = 0;

vector <int> c1, c21, c22;

vector <int> ans;

void print(){

	puts("Yes");

	sort(ans.begin(), ans.end());

	int sz = ans.size();

	printf("%d\n", sz);

	int fg = 0;

	for (auto u : ans){

		if (!fg) fg = 1;

		else putchar(32);

		printf("%d", u);

	}

	putchar(10);

	exit(0);

}

void calc(){

	int x1 = c1.size(), x21 = c21.size(), x22 = c22.size();

	if (k & 1){

		if (num1 == 0){ puts("No"); exit(0);}

		while (k >= 3 && x22 > 0){

			k -= 2;

			--x22;

			ans.push_back(c22[x22]);

			c22.pop_back();

		}

		while (k >= 3 && x21 > 0){

			k -= 2;

			--x21;

			ans.push_back(c21[x21]);

			c21.pop_back();

		}

		while (k > 0 && x1 > 0){

			k--;

			--x1;

			ans.push_back(c1[x1]);

			c1.pop_back();

		}

		if (k > 0){ puts("No"); exit(0); }

		print();

	}

	else{

		while (k >= 2 && x22 > 0){

			k -= 2;

			--x22;

			ans.push_back(c22[x22]);

			c22.pop_back();

		}

		while (k >= 2 && x21 > 0){

			k -= 2;

			--x21;

			ans.push_back(c21[x21]);

			c21.pop_back();

		}

		while (k > 0 && x1 > 0){

			k--;

			--x1;

			ans.push_back(c1[x1]);

			c1.pop_back();

		}

		if (k > 0){ puts("No"); exit(0);}

		print();

	}

}

int main(){

	scanf("%d%d", &n, &k);

	rep(i, 2, 3e5 + 1){

		if (!b[i]){

			for (int j = i + i; j <= 3e5 + 1; j += i)

				b[j] = 1;

		}

	}

	rep(i, 1, 3e5 + 1){

		for (int j = i; j <= 3e5 + 1; j += i) ++f[j];

		--f[i];

	}

	c[1] = 1, c[2] = 1;

	rep(i, n / 2 + 1, n) if (!b[i]){

		if (i <= 2) continue;

		c[i] = 1;

		c1.push_back(i);

		++num1;

	}

	rep(i, n / 3 + 1, n / 2) if (!b[i]){

		if (i <= 2) continue;

		c[i] = 1;

		c[i << 1] = 1;

		c21.push_back(i);

		c22.push_back(i * 2);

		++num2;

	}

	--k;

	ans.push_back(1);

	ans.push_back(2);

	if (k == 0) print();

	rep(i, 3, n){

		if (c[i]) continue;

		if (k >= f[i]){

			k -= f[i];

			ans.push_back(i);

		}

		else calc();

	}

	calc();

	return 0;

}

巴特西

Codeforces 922F Divisibility （构造 + 数论）

最新文章

热门文章