CF1468L - Prime Divisors Selection

Posted on Edited on In

CF1468L - Prime Divisors Selection

题目大意

对于一个序列 \(A\) ，一个合法的质因子序列 \(P\) 满足 \(\forall P_i|A_i,P_i\ is\ a\ prime\)

给定一个序列 \(a_i,i\in[1,n]\) ，求选出 \(k\) 个数，使得对于选出的序列 \(A\)

不存在一个 \(P\) 使得 \(P\) 中某个元素恰好出现一次

\(n\leq 1000,a_i\leq 10^{18}\)


分析

由题目的意思我们知道肯定要分解质因数

Pollard's_Rho!!!

\(10^{18}\) 分解质因数可不是开玩笑的。。。

所以先考虑合法 \(A\) 的判定

判定 \(A\) 合法

假设可以存在一个元素恰好出现一次 \(x\) ，那么在 \(A\) 所有元素质因子中至少要包含一个 \(x\)

并且，不存在两个元素只包含 \(x\)

也就是说，对于合法的 \(A\) 中出现的所有质因子 \(x\) ，都必须存在两个元素只包含 \(x\)

我们称只包含 \(x\) 作为质因子的元素为 \(x\) -元素，为了构造合法的 \(A\) ，我们必须对于一些 \(x\) 选出若干对 \(x\) -元素

对于每个 \(x\) ，我们只把前两个 \(x-\) 元素视为有效，假设有 \(c\) 对这样的元素

那么情况分几种

  1. \(2|k,2c\ge k\) ，那么直接随意选完即合法

  2. \(2c\ge k,2\not |k\) ，此时我们需要选出部分对，使得剩下的元素中存在一个数它的因子集已经被选

枚举剩下一个元素，判定合法即可

  1. \(2c\leq k\) ，此时可以将 \(c\) 对全部选出，判断是否还存在 \(k-2c\) 个可以选择即可


质因数分解

亲身试验，我的Pollards_Rho它T飞了

容易发现，对于 \(x-\) 元素我们只需要找到它的 \(a_i=x^k\)

对于其他元素我们只需要找到 \(a_i\) 对应的 \(x\) 的集合，或者判断无法被 \(x-\) 元素集合包含

由于 \(n\leq 1000\) ，我们可以先得到 \(x-\) 元素集合，其他元素我们最后一个个判定

找到 \(a_i=x^k\) 问题简化了很多

如果你相信std::pow，可以直接来

只需要找到一个最小的 \(k'\) ，使得 \(a_i=x'^{k'}\) ，判定 \(x'\) 是否为质数，如果是则停止，否则继续分解 \(x'\)

对于 \(k'\leq 3\) ，甚至更大一些的情况，std::pow比较可信

而 \(k'>3\) 的情况（实际上 \(k'=4\) 被 \(k'=2\) 包含，所以是 \(k'\ge 5\) ）

实际上 \(x'\) 已经很小了，直接枚举质数即可

素数判定依然需要 \(\text{Miller_Rabin}\) ，但是至少不用Pollards_Rho了

CodeForces Submission

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
const int N=1e5+10;

int n,m;
int pri[N],pc,notpri[N];

ll qmul(ll x,ll y,ll P){
	ull z=(long double)x/P*y+0.5;
	ll res=(ull)x*y-z*P;  Mod2(res);
	return res;
}
ll qpow(ll x,ll k,ll P){
	ll res=1;
	for(;k;k>>=1,x=qmul(x,x,P)) if(k&1) res=qmul(res,x,P);
	return res;
}

int Miller_Rabin(ll n){
	if(n<N) return !notpri[n];
	if(~n&1) return 0;
	ll s=n-1,t=0;
	while(s%2==0) s/=2,t++;
	rep(k,1,7) {
		ll a=qpow(pri[rand()%pc+1],s,n),b;
		rep(i,1,t) {
			b=qmul(a,a,n);
			if(b==1 && a!=1 && a!=n-1) return 0;
			a=b;
		}
		if(a!=1) return 0;
	}
	return 1;
}

ll a[N],mk[N];
vector <ll> F[N]; // Factor Set of each element
vector <ll> IF; // Independent Factor Set
void unique(vector <ll> &a){ sort(a.begin(),a.end()),a.erase(unique(a.begin(),a.end()),a.end()); }

map <ll,vector<int> > M;
ll ans[N];
void Outp(){
	rep(i,1,m) ans[i]=a[ans[i]];
	sort(ans+1,ans+m+1);
	rep(i,1,m) printf("%lld ",ans[i]);
	exit(0);
}

ll Root2(ll n){
	ll x=round(sqrt(n));
	return x*x==n?x:-1;
}
ll Root3(ll n){
	ll x=round(pow(n,1./3));
	return x*x*x==n?x:-1;
}

ll KDivide(ll x){
	if(Miller_Rabin(x)) return x;
	ll y;
	if(~(y=Root2(x))) return KDivide(y);
	if(~(y=Root3(x))) return KDivide(y);
	ll U=pow(x,1./5)+4;
	vector <ll> fac;
	for(int i=1;pri[i]<=U;++i) if(x%pri[i]==0) {
		while(x%pri[i]==0) x/=pri[i];
		fac.pb(pri[i]);
	}
	if(fac.size()==1 && x==1) return fac[0];
	return -1;
}


int main(){
	rep(i,2,N-1) if(!notpri[i]) {
		pri[++pc]=i;
		for(int j=i+i;j<N;j+=i) notpri[j]=1;
	}
	n=rd(),m=rd();
	rep(i,1,n) {
		ll x=KDivide(a[i]=rd<ll>());
		if(~x) IF.pb(x);
	}
	unique(IF);
	rep(i,1,n) {
		ll x=a[i];
		for(ll y:IF) if(x%y==0) {
			while(x%y==0) x/=y;
			F[i].pb(y);
		}
		if(x>1) F[i].pb(-1),F[i].pb(-2); // invalid factor, emm... to avoid some situation we push two 
		if(F[i].size()==1 && M[F[i][0]].size()<2) M[F[i][0]].pb(i),mk[i]=1;
	}
	int c=0;
	for(auto i:M) if(i.second.size()>=2) c++;
	if(m%2==0 && c*2>=m) {
        // choose k/2 pairs!!
		int k=m;
		for(auto i:M) if(i.second.size()>=2) {
			if(!k) break;
			rep(j,0,1) ans[k--]=i.second[j];
		}
		Outp();
	}
	if(c*2>=m) {
        // find another
		rep(i,1,n) if(!mk[i] && (int)F[i].size()<=m/2) {
			int f=1;
			for(ll x:F[i]) if(M[x].size()<2) f=0;
			if(f) {
				int k=m;
				ans[k--]=i;
				for(ll x:F[i]) {
					rep(j,0,1) ans[k--]=M[x][j];
					M.erase(x);
				}
				for(auto i:M) if(i.second.size()>=2) {
					if(!k) break;
					rep(j,0,1) ans[k--]=i.second[j];
				}
				Outp();
			}
		}
	} else {
		int k=m;
		for(auto i:M) if(i.second.size()>=2) {
			if(!k) break;
			rep(j,0,1) ans[k--]=i.second[j];
		}
        // Count if we have left much enough...
		rep(i,1,n) if(!mk[i]) {
			if(!k) break;
			int f=1;
			for(ll x:F[i]) if(M[x].size()<2) f=0;
			if(f) ans[k--]=i;
		}
		if(!k) Outp();
	}
	puts("0");
}