CF1148G Gold Experience

神仙题。大概是一篇只有做法没有思路的题解。。

显然这个题 $\gcd > 1$ 就是想建补图。然后问题就变成了选出一个点集使得大小正好为 $k$ 且要么每个点都在导出子图里有边,要么所有点都是孤立点。构造一组方案即可。

需要注意的是第二种情况,如果可以找到一个 $\ge k$ 的独立集,那么只需要保留 $k$ 个点即可。

首先要会求所有点的度数。不难发现 $a_i$ 的度数是

其中 $occ[k]$ 是 $k$ 这个数在 $A$ 中的出现次数。这个东西可以通过把所有数变成 square free 之后集合枚举,并且预处理 $G[t] = \sum_{j|t} occ[j]$,算出所有数的度数的时间是 $O(2^8 n)$ 。

我们可以提前提出 $3$ 个点有边相连的点来(原因在后面)。具体来说,如果存在一个点度数 $\ge 2$ ,我们直接拿它以及相邻的点出来。

如果所有点度数都不到 $2$ ,也就是说整张图构成了一个匹配,就可以非常方便地构造出一个 $\ge \frac n 2$ 的独立集,直接从每个匹配里面拿一端,然后拿掉所有孤立的点。具体做法可以一个一个点枚举,如果之前枚举到的点没有一个与当前点互质的就可以加入答案,否则跳过。这个的做法类似于求度数。

现在可以假装已经拿出了一个三元组满足它们有连边了。我们考虑删除这个三元组后剩下的东西。如果独立的点的个数已经 $\ge k$ ,那么显然可以直接输出独立的点。

否则,设 $t$ 为独立的点的个数,那么总共的有边相连的点的个数是

这个保证我们一定可以构造出解来。

设 $f(i)$ 表示只考虑前 $i$ 个点的导出子图,能够得到的有边相连的点的个数。由于上面的计算,已经有 $f(n) + 3 \ge k$ 了。而且显然地, $f(i)$ 是一个不减的函数。所以我们可以二分出一个位置 $p$ ,满足

然后考虑怎么通过前 $p$ 个点的导出子图来构造出正好 $k$ 个点的解。

我们先把前 $p$ 个点的导出子图求出来,然后考虑删除一些点使得这个图正好是 $k$ 。我们考虑与 $p$ 相连的点,显然它不会是一个独立点(否则 $f(p) = f(p-1)$ ),显然有 $f(p) - f(p-1) - 1$ 个。 但是并不能把这些点全部删光,否则 $p$ 就独立了。所以在这里可以丢掉的有 $f(p) - f(p-1) - 2$ 个点,然后这个导出子图的点的个数就最小可以变成

也就是说通过这个方法我们可以构造出 $[f(p-1)+5,f(p)+3]$ 的任意值。但是 $k > f(p-1) + 3$ ,如果 $k = f(p-1) + 4$ 呢?这个时候之前保留的三个点就有用了,直接从中删除一个即可。

于是这题就做完了。复杂度 $O(n\log n 2^8 + n\log v)$ 。实际上跑的很快。

代码写得非常丑,不建议参考

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "vector"
#include "set"
#include "map"
#include "bitset"
#include "cmath"
#include "ctime"
#include "unordered_map"
#include "queue"
using namespace std;
#define rep( i , a , b ) for( int i = a , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = a , i##end = b ; i >= i##end ; -- i )
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define all( a ) a.begin() , a.end()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
const int MAXN = 2e5 + 6;
typedef long long ll;
const int P = 998244353;
int n , k;

int pri[10000006] , mnp[10000006] , mu[10000006] , cn = 0;
void sieve( ) {
mu[1] = 1;
rep( i , 2 , 1e7 ) {
if( !pri[i] ) pri[++cn] = i , mu[i] = -1 , mnp[i] = i;
for( int j = 1 ; j <= cn && pri[j] * i < 10000000 ; ++j ) {
mnp[i * pri[j]] = pri[j] , pri[i * pri[j]] = 1;
if( i % pri[j] == 0 ) { mu[i * pri[j]] = 0; break; }
mu[i * pri[j]] = -mu[i];
}
}
}

int buc[10000006];
vi lsj[MAXN];
int deg[MAXN];
int A[MAXN];
set<int> zzh;
int era[MAXN];
void caldeg( int r ) {
rep( i , 1 , r ) if( !era[i] ) for( int x : lsj[i] ) ++ buc[x];
rep( i , 1 , n ) deg[i] = 0;
rep( i , 1 , r ) if( !era[i] ) {
for( int x : lsj[i] ) deg[i] += mu[x] * buc[x];
}
rep( i , 1 , r ) if( !era[i] ) for( int x : lsj[i] ) buc[x] = 0;
}
int cal( int r ) {
caldeg( r );
int as = 0;
rep( i , 1 , r ) if( deg[i] ) {
++ as;
}
return as;
}

int W[300];
int gcd( int a , int b ) {
return !b ? a : gcd( b , a % b );
}

void solve() {
cin >> n >> k;
rep( i , 1 , n ) scanf("%d",A + i);
rep( i , 1 , n ) {
vi f;
int c = A[i];
while( c != 1 ) {
int p = mnp[c];
f.pb( p );
while( c % p == 0 ) c /= p;
}
W[0] = 1;
lsj[i].pb( 1 );
for( int t = 1 ; t < ( 1 << f.size() ) ; ++ t )
W[t] = W[t ^ ( t & -t )] * f[__builtin_ctz( t )] , lsj[i].pb( W[t] );
}
int ff = 0;
caldeg( n );
int ng = 0 , fk = 0;
rep( i , 1 , n ) {
if( deg[i] == 0 ) ++ ng , era[i] = 1;
if( deg[i] > 2 ) fk = i;
}
if( ng >= k ) {
vi as;
rep( i , 1 , n ) if( deg[i] == 0 ) as.pb( i );
as.resize( k );
for( int x : as ) printf("%d ",x); puts("");
return;
}
if( !fk ) {
vi as;
rep( i , 1 , n ) {
int re = 0;
for( int x : lsj[i] ) re += mu[x] * buc[x] , ++ buc[x];
if( !re ) as.pb( i );
}
as.resize( k );
for( int x : as ) printf("%d ",x); puts("");
return;
}
vi as;
era[fk] = 1;
as.pb( fk );
int ccn = 1;
rep( i , 1 , n ) if( i != fk ) {
if( gcd( A[i] , A[fk] ) == 1 )
++ ccn , era[i] = 1 , as.pb( i );
if( ccn == 3 ) break;
}
caldeg( n );
ng = 0;
rep( i , 1 , n ) if( deg[i] == 0 && !era[i] ) ++ ng;
if( ng >= k ) {
as.clear();
rep( i , 1 , n ) if( deg[i] == 0 && !era[i] ) as.pb( i );
as.resize( k );
for( int x : as ) printf("%d ",x); puts("");
return;
}
rep( i , 1 , n ) if( deg[i] == 0 ) era[i] = 1;
as.resize( 3 );
int l = 0 , r = n - 1;
while( l <= r ) {
int mid = l + r >> 1;
if( cal( mid ) + 3 >= k ) r = mid - 1;
else l = mid + 1;
}
++ r;
int t = cal( r );
int ned = t + 3 - k , las = 0 , s = 0;
rep( i , 1 , r ) if( deg[i] ) {
if( gcd( A[i] , A[t] ) == 1 ) {
if( s < ned ) deg[i] = 0 , las = i;
++ s;
}
}
if( s == ned && s ) deg[las] = 1 , as.pop_back();
rep( i , 1 , r ) if( deg[i] ) as.pb( i );
for( int x : as ) printf("%d ",x); puts("");
}

signed main( ) {
sieve();
// int T;cin >> T;while( T-- ) solve();
solve();
}

文章作者: yijan
文章链接: https://yijan.co/2021/02/17/cf1148g-gold-experience/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog