Submission #64409745

---

Source Code Expand

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int solve(int M, int K) {
	vector<int> primes;
	for (int i = 2; i <= M; i++) {
		bool f = true;
		for (int j = 2; j * j <= i; j++) {
			if (i % j == 0) {
				f = false;
			}
		}
		if (f) {
			primes.push_back(i);
		}
	}
	int Z = primes.size();
	vector<vector<int> > flag(M + 1, vector<int>(Z, 0));
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < Z; j++) {
			flag[i][j] = int(i % primes[j] == 0);
		}
	}
	for (int num = M; num >= 1; num--) {
		auto dfs = [&](auto& self, int pos, int cnt, vector<int> cur) -> bool {
			if (cnt > num || cnt + ((M + 1) - pos) < num) {
				return false;
			}
			if (pos == M + 1) {
				return true;
			}
			if (self(self, pos + 1, cnt, cur)) {
				return true;
			}
			for (int i = 0; i < Z; i++) {
				cur[i] += flag[pos][i];
				if (cur[i] >= K) {
					return false;
				}
			}
			if (self(self, pos + 1, cnt + 1, cur)) {
				return true;
			}
			return false;
		};
		if (dfs(dfs, 1, 0, vector<int>(Z, 0))) {
			return num;
		}
	}
	return 0;
}

vector<int> greedy(int M, int K) {
	vector<bool> isprime(M + 1, true);
	isprime[0] = false;
	isprime[1] = false;
	for (int i = 2; i <= M; i++) {
		if (isprime[i]) {
			for (int j = i * 2; j <= M; j += i) {
				isprime[j] = false;
			}
		}
	}
	vector<int> primes;
	for (int i = 2; i <= M; i++) {
		if (isprime[i]) {
			primes.push_back(i);
		}
	}
	int Z = primes.size();
	vector<int> remain(Z, K - 1);
	vector<int> ans = {1};
	for (int i = 0; i < Z; i++) {
		long long x = primes[i];
		while (x <= M && remain[i] != 0) {
			ans.push_back(int(x));
			remain[i]--;
			x *= primes[i];
		}
	}
	for (int i = 0; i < Z - 1; i++) {
		if (1LL * primes[i] * primes[i + 1] <= M) {
			int pos = Z - 1;
			while (pos > i && remain[i] != 0) {
				if (remain[pos] > 0 && 1LL * primes[i] * primes[pos] <= M) {
					long long x = primes[i];
					while (x * primes[pos] <= M && remain[i] != 0 && remain[pos] != 0) {
						long long y = x * primes[pos];
						while (y <= M && remain[i] != 0 && remain[pos] != 0) {
							ans.push_back(int(y));
							remain[i]--;
							remain[pos]--;
							y *= primes[pos];
						}
						x *= primes[i];
					}
				}
				pos--;
			}
		}
	}
	sort(ans.begin(), ans.end());
	return ans;
}

void solver() {
	int M, K;
	cin >> M >> K;
	vector<int> ans = greedy(M, K);
	cout << ans.size() << endl;
	for (int i = 0; i < int(ans.size()); i++) {
		if (i != 0) {
			cout << ' ';
		}
		cout << ans[i];
	}
	cout << endl;
}

int main() {
	solver();
	return 0;
	/*
	for (int M = 1; M <= 100; M++) {
		cout << M << ":";
		for (int K = 2; K <= 5; K++) {
			int res = greedy(M, K).size();
			cout << ' ' << res;
		}
		cout << endl;
	}
	*/
	return 0;
}

Submission Info

Judge Result