这种区间反转的题，套路就是差分。
设 a i a_i ai 表示第 i i i 枚硬币是否正面朝上，显然只有 a x 1 , a x 2 , ⋯ , a x n a_{x_1},a_{x_2},cdots,a_{x_n} ax1,ax2,⋯,axn 等于 1 1 1，其他都是 0 0 0。那么我们的目标是把 a a a 数组全部变成 0 0 0。
设 b i b_i bi 表示第 i i i 枚硬币和第 i − 1 i-1 i−1 枚硬币是否不同，即 b i = a i xor a i − 1 b_i=a_ioperatorname{xor} a_{i-1} bi=aixorai−1。那么我们的目标就变成了把 b b b 数组全部变成 0 0 0，即让每个数都相同。
设 prime extit{prime} prime 为所有奇数质数的集合， p ∈ prime pin extit{prime} p∈prime，那么一次反转可以看做将 a i ∼ a i + p − 1 a_isim a_{i+p-1} ai∼ai+p−1 全部取反。
发现将 a i ∼ a i + p − 1 a_isim a_{i+p-1} ai∼ai+p−1 取反后其实等价于 b i b_i bi 和 b i + p b_{i+p} bi+p 两个数取反。
所以现在操作就变成了：任意选择两个正整数 i , j i,j i,j，且满足 j − i ∈ prime j-iin extit{prime} j−i∈prime，然后将 b i b_i bi 和 b j b_j bj 取反。
然后在所有值为枚举满足 b i = b j = 1 b_i=b_j=1 bi=bj=1 的任意一对 i , j i,j i,j（ i < j i<j i<j），考虑如何操作才能将 b i b_i bi 和 b j b_j bj 都变为 0 0 0 且操作数最少，分情况讨论：
-
j − i ∈ prime j-iin extit{prime} j−i∈prime。此时我们可以直接将 b i b_i bi 和 b j b_j bj 变为 0 0 0，共 1 1 1 次操作。
-
j − i j-i j−i 为正偶数。
那么当 j − i = 2 j-i=2 j−i=2 时，我们可以对 b i b_i bi、 b i + 5 b_{i+5} bi+5 取反，然后再对 b i + 2 b_{i+2} bi+2、 b i + 5 b_{i+5} bi+5 取反，共 2 2 2 次操作；
当 j − i = 4 j-i=4 j−i=4 时，我们可以对 b i b_i bi、 b i + 7 b_{i+7} bi+7 取反，然后再对 b i + 4 b_{i+4} bi+4、 b i + 7 b_{i+7} bi+7 取反，共 2 2 2 次操作；
当 j − i j-i j−i 为其他正偶数时，由哥德巴赫猜想在 1 0 7 10^7 107 范围内的正确性，可知 j − i j-i j−i 可以分为两个奇质数的和。即存在 p 1 + p 2 = j − i p_1+p_2=j-i p1+p2=j−i，且 p 1 , p 2 ∈ prime p_1,p_2in extit{prime} p1,p2∈prime。那么我们可以对 b i b_i bi、 b i + p 1 b_{i+p_1} bi+p1 取反，然后再对 b i + p 1 b_{i+p_1} bi+p1、 b i + p 1 + p 2 b_{i+p_1+p_2} bi+p1+p2 取反，共 2 2 2 次操作。
综述，当 j − i j-i j−i 为正偶数时，最小的操作数都是 2 2 2 次。 ( 2 ) (2) (2)
-
j − i j-i j−i 为除 prime extit{prime} prime 以外的正奇数。
当 j − i = 1 j-i=1 j−i=1 时，我们可以对 b i b_i bi、 b i + 7 b_{i+7} bi+7 取反，然后对 b i + 4 b_{i+4} bi+4、 b i + 7 b_{i+7} bi+7 取反，对 b i + 1 b_{i+1} bi+1、 b i + 4 b_{i+4} bi+4 取反，共 3 3 3 次操作。
类似地，可知当 j − i = 3 j-i=3 j−i=3 时，也存在一种方案且最小操作数为 3 3 3。
当 j − i j-i j−i 为其他正奇数时，即 j − i > 3 j-i>3 j−i>3 且 j − i j-i j−i 为奇数时，我们可以将 j − i j-i j−i 分解成 “ 3 + 正偶数 3+ ext{正偶数} 3+正偶数” 的形式，然后再由 ( 2 ) (2) (2) 得此时最少的操作数为 3 3 3 次。
综述，当 j − i j-i j−i 为除 prime extit{prime} prime 以外的正奇数时，最小的操作数都是 3 3 3 次。
所以为了使得操作数最少，我们应该优先使用第 1 1 1 种情况。
设有 k k k 个 b i = 1 b_i=1 bi=1，并且将他们的下标用集合 S = { c 1 , c 2 , ⋯ , c k } S={c_1,c_2,cdots,c_k} S={c1,c2,⋯,ck} 表示。
那么 k k k 肯定是偶数，因为考虑将 a i a_i ai 中连续的 1 1 1 当做一个块。那么对于每个块 a head ∼ a tail a_{ extit{head}}sim a_{ extit{tail}} ahead∼atail，块头贡献一个 b head = 1 b_{ extit{head}}=1 bhead=1，块尾贡献一个 b tail + 1 b_{ extit{tail}+1} btail+1，所以总贡献就是偶数个。
发现如果有 c i − c j ∈ prime c_i-c_jin extit{prime} ci−cj∈prime，那么 c i c_i ci 和 c j c_j cj 的奇偶性必定不同。
于是想到将 c i c_i ci 奇偶分类，并对于所有的 c i − c j ∈ prime c_i-c_jin extit{prime} ci−cj∈prime，连边 ( i , j ) (i,j) (i,j)，那么这就是一个二分图的形式。
显然对这个二分图跑最大匹配就是第 1 1 1 种情况的最多使用数。
将这些点取反之后，还剩下一些点需要取反，于是考虑使用第 2 2 2 种情况。
显然，若 c i − c j c_i-c_j ci−cj 为正偶数，那么 c i c_i ci 和 c j c_j cj 的奇偶性相同。
所以将奇类中剩下的 c i c_i ci 进行两两取反，将偶类中剩下的 c i c_i ci 进行两两取反。
然后再考虑第 3 3 3 种情况，此时奇类和偶类肯定要么都剩下 0 0 0 个未取反、要么都剩下 1 1 1 个未取反，因为 k k k 为偶数。然后对于各剩下 1 1 1 个未取反的情况下，将他们两个按第 3 3 3 种情况处理。
将 3 3 3 种情况的总操作数加起来，就是最后的答案了。
代码如下：
#include<bits/stdc++.h>
#define N 110
#define INF 0x7fffffff
using namespace std;
int n,a[N];
int tot,odd,b[N<<1];
int cnt=1,head[N<<1],cur[N<<1],nxt[N*N*8+N*4],to[N*N*8+N*4],c[N*N*8+N*4];
int s,t,num[N<<1];
queue<int>q;
void adde(int u,int v,int ci)
{
to[++cnt]=v;
c[cnt]=ci;
nxt[cnt]=head[u];
head[u]=cnt;
to[++cnt]=u;
c[cnt]=0;
nxt[cnt]=head[v];
head[v]=cnt;
}
bool check(int x)//判断一个数是否属于prime
{
if(x<=2) return false;
if(!(x&1)) return false;
for(int i=2,maxn=sqrt(x);i<=maxn;i++)
if(!(x%i)) return false;
return true;
}
bool bfs()
{
memcpy(cur,head,sizeof(cur));
memset(num,-1,sizeof(num));
q.push(s);
num[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]&&num[v]==-1)
{
num[v]=num[u]+1;
q.push(v);
}
}
}
return num[t]!=-1;
}
int dfs(int u,int minflow)
{
if(u==t||!minflow) return minflow;
int preflow=0,nowflow;
for(int i=cur[u];i;i=nxt[i])
{
cur[u]=i;
int v=to[i];
if(num[v]==num[u]+1&&(nowflow=dfs(v,min(c[i],minflow-preflow))))
{
preflow+=nowflow;
c[i]-=nowflow;
c[i^1]+=nowflow;
if(!(minflow-preflow)) break;
}
}
return preflow;
}
int dinic()//用dinic跑最大匹配
{
int maxflow=0;
while(bfs())
maxflow+=dfs(s,INF);
return maxflow;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
b[++tot]=a[1];
for(int i=2;i<=n;i++)
{
if(a[i]-a[i-1]>1)
{
b[++tot]=a[i-1]+1;//块尾贡献
b[++tot]=a[i];//块头贡献
}
}
b[++tot]=a[n]+1;
s=1,t=1+tot+1;
for(int i=1;i<=tot;i++)
{
if(b[i]&1)
{
odd++;
adde(s,1+i,1);
for(int j=1;j<=tot;j++)
if(check(abs(b[i]-b[j]))) adde(1+i,1+j,1);
}
else adde(1+i,t,1);
}
int sum1=dinic();
printf("%d
",sum1+(odd-sum1)/2*2+((tot-odd)-sum1)/2*2+((odd-sum1)&1)*3);
return 0;
}