前置知识：
二分图匹配，基础数论
题意：
给定 n n n个数，选出最大的子集，使得满足子集中的任意两个元素满足： g c d ( a i , a j ) ∗ g c d ( a i + 1 , a j + 1 ) ! = 1 gcd(a_i,a_j)*gcd(a_i+1,a_j+1)!=1 gcd(ai,aj)∗gcd(ai+1,aj+1)!=1， n ≤ 500 n\leq 500 n≤500
题解：
最直接的想法就是，满足条件的点之间建立一条边，那么满足条件的一定是一个完全图，但是没有特别的方法去找到图中的最大一个完全图，而且这样会很麻烦。
正难则反！！！
考虑给图中不满足条件的建边，即满足 g c d ( a i , a j ) ∗ g c d ( a i + 1 , a j + 1 ) = = 1 gcd(a_i,a_j)*gcd(a_i+1,a_j+1)==1 gcd(ai,aj)∗gcd(ai+1,aj+1)==1的点对建立一条边。按照这样的方法建边有什么特别的性质呢？
该图是一个二分图！！
显然奇数和奇数以及偶数和偶数之间是不会存在边的。因为 g c d ( a i , a j ) ∗ g c d ( a i + 1 , a j + 1 ) gcd(a_i,a_j)*gcd(a_i+1,a_j+1) gcd(ai,aj)∗gcd(ai+1,aj+1)至少为2以上。形成的环必定是奇偶数相间的，且至少是偶数个数，所以不存在奇环。必定是一个二分图。
我们由二分图最大独立集可知，该集合中的所有的集合任意两点是不存在连边的，而二分图的最大独立集为 n n n-最大匹配数。
总结：
这题的难点在于建边，如果想出怎么建边，而二分图求解答案的思路就顺其自然了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int mp[N][N];
int n,a[N],vis[N],ans,p[N];
bool match(int i) {
for(int j=1; j<=n; j++) {
if(mp[i][j]&&!vis[j]) {
vis[j]=true;
if(p[j]==0||match(p[j])) {
p[j]=i;
return true;
}
}
}
return false;
}
signed main() {
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(__gcd(a[i],a[j])==1&&__gcd(a[i]+1,a[j]+1)==1) mp[i][j]=1;
for(int i=1; i<=n; i++) {
memset(vis,0,sizeof vis);
if(match(i)) ans++;
}
ans/=2;ans=n-ans;
cout<<ans;
return 0;
}