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$，此时我们需要选出部分对，使得剩下的元素中存在一个数它的因子集已经被选

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

3.$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

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");
}