题意：

一个可重集合中包含n个元素 $a1,a2,……,an$，你需要选择一个子集，使得这个子集中任意两个元素 $a_i,a_j$均满足条件$gcd(ai,aj)*gcd(ai+1,aj+1)≠1$，且这个子集的元素个数是所有满足上述条件的子集中最多的。输出这个子集的元素个数。

思路：

挺经典的一道题。

看这道题就可以想到最大团。

最大团就是图的最大的完全子图（每两个点之间都有边相连）。

这里满足 $gcd(ai,aj)*gcd(ai+1,aj+1)≠1$的每两个$a_i,a_j$都用边相连，该图的最大团就是题目所求了。

如何求最大团呢？

最大团=补图的最大独立集。最大独立集数目=|V|−最大匹配数。

该图的补图就是对满足$gcd(ai,aj)*gcd(ai+1,aj+1)=1$的每两个$a_i,a_j$用边相连。

然后二分图匹配就可以了。

有一个小优化，奇数和奇数，偶数和偶数肯定是不用连边的，只要连奇数和偶数就好了。

看别人还有一种做法，多次random_shuffle取满足条件的一个一个加到答案里。

以后如果看到两两满足条件这种题目的的话，可以试着从这种角度来做。

代码：

int n;
ll a[510];
vector<int>v[510];
bool vis[510];
int link[510];
ll gcd(ll a,ll b)
{
    if(a<b){ll temp;temp=a;a=b;b=temp;}
    while(a%b){ll r=a%b;a=b;b=r;}
    return b;
}
bool judge(int id)
{
    for(int i=0;i<v[id].size();i++)
    {
        int temp=v[id][i];
        if(!vis[temp])
        {
            vis[temp]=true;
            if(link[temp]==-1||judge(link[temp]))
            {
                link[temp]=id;
                return true;
            }
        }
    }
    return false;
}
int maxmatch()
{
    memset(link,-1,sizeof(link));
    int num=0;
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(judge(i))
            num++;
    }
    return num;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
        {
            if(gcd(a[i],a[j])*gcd(a[i]+1,a[j]+1)==1)
            {
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    printf("%d\n",n-maxmatch()/2);
    return 0;
}