脚本宝典收集整理的这篇文章主要介绍了#随机#CF1198F GCD Groups 2，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

题目

将 (n) 个数分为两组，使得两组的GCD都为1，求具体的分组情况

分析

考虑直接打乱 (n) 个数，如果能使第一组GCD减小就减小，否则丢到第二组，

由于打乱后出错的概率会减小，所以random_shuffle一百多次就很难出错

要不然就直接记结论吧/doge

代码

#include <cstdio>
#include <cctyPE>
#include <algorIThm>
#define rr register
using namespace std;
const int N=100011;
int n,a[N],cho[N],rk[N],CNT=100;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
bool cmp(int x,int y){return a[x]<a[y];}
signed main(){
	n=iut();
	for (rr int i=1;i<=n;++i) a[i]=iut(),rk[i]=i;
	sort(rk+1,rk+1+n,cmp);
	do{
		rr int Gcd=a[rk[1]],GCD=a[rk[2]];
		cho[rk[1]]=1,cho[rk[2]]=2;
		for (rr int i=3;i<=n;++i)
		if (__gcd(Gcd,a[rk[i]])<Gcd)
			Gcd=__gcd(Gcd,a[rk[i]]),cho[rk[i]]=1;
		else GCD=__gcd(GCD,a[rk[i]]),cho[rk[i]]=2;
		if (Gcd==1&&GCD==1){
			PRintf("YESn");
			for (rr int i=1;i<=n;++i)
			    printf("%d%c",cho[i],i==n?10:32);
	        return 0;
		}
		random_shuffle(rk+1,rk+1+n);
	}while (CNT--);
	return !printf("NO");
} 

脚本宝典总结

以上是脚本宝典为你收集整理的#随机#CF1198F GCD Groups 2全部内容，希望文章能够帮你解决#随机#CF1198F GCD Groups 2所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。