简要题意
给出一个长度为 \(n\) 的序列 \(a\)。你需要选出它的一个子集 \(S\)。使其满足对于任意两个元素 \(i,j\)。满足：
\[\gcd(i,j)\cdot\gcd(i+1,j+1)\neq1
\]
输出满足条件的子集大小的最大值。
\(1 \leq n \leq 500,1 \leq a_i \leq 10^{18}\)
思路
这道题比 Codeforces Gym 104059B - Breeding Bugs 更为简单。
首先对于选出一个子集两两满足特定约束的问题，有一个经典思路就是将满足条件转换为不满足条件，然后对于不满足条件的两个点连一条边，答案就是最大独立集。
但是一般图最大独立集是 NPC 问题。考虑发掘这张图的特殊性质。
引理：若 \(i\equiv j\pmod{2}\)，则 \(\gcd(i,j)\cdot\gcd(i+1,j+1)\neq1\)。（但是这个命题的假命题不成立）。
Proof：若 \(i\equiv j\pmod{2}\)，则 \(\gcd(i,j)\equiv0\pmod{2}\)，所以上式必定不为 \(1\)。得证。
于是我们可以按照奇偶性黑白染色，就可以把原图变成二分图了。
然后用匈牙利即可。
代码
#include<bits/stdc++.h>
#define gcd __gcd
#define int long long
using namespace std;
const int N = 505;
int n;
struct edge{
int nxt,to;
} g[N*N];
int head[N],ec,a[N],mch[N],vist[N];
void add(int u,int v){
g[++ec].nxt=head[u];
g[ec].to=v;head[u]=ec;
}
bool dfs(int u,int tag){
if(vist[u]==tag) return 0;
vist[u]=tag;
for(int i=head[u];i;i=g[i].nxt){
int v=g[i].to;
if(!mch[v] || dfs(mch[v],tag)){
mch[v]=u;
return 1;
}
}
return 0;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
if(!(a[i]&1)) continue;
for(int j=1;j<=n;j++){
if(a[j]&1) continue;
if(gcd(a[i],a[j])*gcd(a[i]+1,a[j]+1)==1){
add(i,j);
}
}
}
int ans=n;
for(int i=1;i<=n;i++){
if(dfs(i,i)) ans--;
}
cout<<ans;
return 0;
}