题目
将 \(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("YES\n");
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");
}