CF1198F GCD Groups 2
eee_hoho
2021-03-23 21:50:15
这是Div1F¿我人傻了。
一看到这题完全不会怎么办啊，那就直接随机好了。
先考虑一种贪心思路，加入一个数 $a$ 的时候，加入到一个 $gcd$ 不是 $a$ 的因子的集合，这样子 $\gcd$ 一定变小了，变得很优。
然而这肯定过不去，所以多随机几遍 $a$ 加入的顺序，就能得到解了。
思考一下这样做的正确性，我们注意到 $a$ 的质因子最多只有 $9$ 个，那么什么时候我们这样子做会错误，就是其中一个集合存在一个公共质因子，而 $10^9$ 以内的质数大约有 $5\times 10^7$ 个，所以这样的概率是非常低的，于是就做完了。
**Code**
``` cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1e5;
const int inf = 1e8;
using namespace std;
int n,a[N + 5],g[3],c[N + 5],id[N + 5];
bool solve()
{
c[id[1]] = 1;
g[1] = a[id[1]];
c[id[2]] = 2;
g[2] = a[id[2]];
for (int i = 3;i <= n;i++)
{
if (a[id[i]] % g[1] == 0)
{
c[id[i]] = 2;
g[2] = __gcd(g[2],a[id[i]]);
}
else
{
c[id[i]] = 1;
g[1] = __gcd(g[1],a[id[i]]);
}
}
return g[1] == 1 && g[2] == 1;
}
int main()
{
srand(19260817);
scanf("%d",&n);
for (int i = 1;i <= n;i++)
scanf("%d",&a[i]),id[i] = i;
int fl = 0,T = inf / n / 20;
T = min(T,2000);
while (T--)
{
g[1] = g[2] = 0;
random_shuffle(id + 1,id + n + 1);
fl |= solve();
if (fl)
{
cout<<"YES"<<endl;
for (int i = 1;i <= n;i++)
printf("%d ",c[i]);
return 0;
}
}
cout<<"NO"<<endl;
return 0;
}
```