CF1148G Gold Experience

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

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

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

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

1jvocc[j][gcd(ai,aj)=1]=taiμ(t)tjocc[j]\sum_{1 \le j \le v} occ[j][\gcd(a_i,a_j) = 1]\\ =\sum_{t | a_i} \mu(t) \sum_{t | j} occ[j]

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

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

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

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

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

n3tn3(k1)n2kn-3-t \ge n-3-(k-1) \ge n-2-k

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

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

f(p)+3k>f(p1)+3f(p) + 3 \ge k > f(p-1) + 3

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

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

f(p)+3(f(p)f(p1)2)=f(p1)+5f(p) + 3 - (f(p) - f(p-1)-2) = f(p-1) + 5

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

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

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

#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();
}

\