Codeforces 922F Divisibility 构造

Divisibility

我们考虑删数字

首先我们可以发现有一类数很特殊就是大于 n / 2的素数, 因为这些素数的贡献只有1, 并且在n大的时候,

这些素数的个数不是很少, 我们可以最后用这些数去调整, 并且删掉一个数的时候删掉的是它的因子个数,

所以可以用素数去控制最后的数量。当n小的时候直接状压枚举。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 1e6 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-;
const double PI = acos(-); int n;
LL k;
int rel[N];
bool vis[N];
int now;
vector<int> vc;
set<int> Set;
vector<int> fac[N]; int main() {
scanf("%d%lld", &n, &k);
if(n <= ) {
vector<int> ret;
for(int S = ; S < ( << n); S++) {
ret.clear();
for(int i = ; i < n; i++)
if(S >> i & ) ret.push_back(i + );
int cnt = ;
for(int i = ; i < SZ(ret); i++) {
for(int j = i + ; j < SZ(ret); j++) {
if(ret[j] % ret[i] == ) {
cnt++;
}
}
}
if(cnt == k) {
puts("Yes");
printf("%d\n", SZ(ret));
for(auto& t : ret) printf("%d ", t);
puts("");
return ;
}
}
puts("No");
} else {
for(int i = ; i <= n; i++) {
for(int j = i + i; j <= n; j += i)
vis[j] = true;
}
for(int i = ; i <= n; i++) Set.insert(i);
for(int i = ; i <= n; i++) {
for(int j = i + i; j <= n; j += i) {
now++;
rel[j]++;
rel[i]++;
fac[j].push_back(i);
}
}
if(now < k) {
puts("No");
return ;
}
if(now == k) {
puts("Yes");
printf("%d\n", SZ(Set));
for(auto& t : Set) printf("%d ", t);
puts("");
return ;
}
for(int i = n / + ; i <= n; i++) {
if(!vis[i]) {
vc.push_back(i), now--, Set.erase(i);
rel[]--;
if(now == k) {
puts("Yes");
printf("%d\n", SZ(Set));
for(auto& t : Set) printf("%d ", t);
puts("");
return ;
}
}
}
while(now > k) {
int v = *Set.rbegin();
if(rel[v] <= now - k) {
now -= rel[v];
Set.erase(v);
for(auto& t : fac[v]) rel[t]--;
} else {
int who = v;
for(auto& t : Set)
if(now - rel[t] <= k && rel[t] < rel[who]) who = t;
now -= rel[who];
Set.erase(who);
for(auto& t : fac[who]) rel[t]--;
while(now < k && SZ(vc)) {
now++;
Set.insert(vc.back());
vc.pop_back();
}
}
}
if(now == k) {
puts("Yes");
printf("%d\n", SZ(Set));
for(auto& t : Set) printf("%d ", t);
puts("");
return ;
} else {
puts("No");
}
}
return ;
} /*
*/
上一篇:SQL远程备份


下一篇:docker registry push错误“server gave HTTP response to HTTPS client”