You are given an array of 𝑛 integers. You need to split all integers into two groups so that the GCD of all integers in the first group is equal to one and the GCD of all integers in the second group is equal to one.

The GCD of a group of integers is the largest non-negative integer that divides all the integers in the group.

Both groups have to be non-empty.

大致题意 📖

给你NN 个数,求一种方法使得将这NN个数分成两堆,每堆的GCDGCD都为11

链接 🔗

「CodeForces 1198F」GCD Groups 2

题解 ❓

随机数 + 贪心
随机生成数列顺序,然后贪心,如果丢左堆,能使得左堆gcd变小,则丢左堆,否则丢右堆

代码

const ll maxd = 4e5+10;
ll a[maxd],b[maxd],ans[maxd];
int main()
{
//    __IN;__OUT;
    ll n;RLL(n);
    FOR(i,1,n) RLL(a[i]);
    FOR(i,1,n) b[i] = i;
    clock_t st = clock();
    while(clock() - st  < 0.4 * CLOCKS_PER_SEC) // 时限小于0.4s时
    {
        random_shuffle(b+1,b+1+n); // 将随机打乱顺序
        ll x = 0 , y = 0;
        FOR(i,1,n)
        {
            ll t = gcd(x,a[b[i]]);
            if(t == x) y = gcd(a[b[i]],y),ans[b[i]] = 2;
            else x = t, ans[b[i]] = 1;
        }
        if(x == 1 && y == 1)
        {
            PS("YES");
            FOR(i,1,n) PLP(ans[i]);
            return 0;
        }
    }
    PS("NO");
    return 0;
}