ARC080F

题目大意：

有无限枚硬币，其中有\(N\)枚硬币\(x_{1\ldots N}\)初始时正面朝上，其余均为背面朝上，每次可以选择一段区间\([l,r]\)，将区间内所有硬币翻转，其中\(r-l+1\)为一个奇数质数；问最少多少次能将所有硬币全部翻为背面朝上。

• $ 1\ <\ =\ N\ <\ =\ 100 $
• $ 1\ <\ =\ x_1\ <\ x_2\ <\ …\ <\ x_N\ <\ =\ 10^7 $

一个很容易想到的思路就是把硬币看成正着的事 \(1\) ，反面是 \(0\) ，做一个异或前缀和

即初始，对于数组 \(a\) ，\(a_{x_1} = 1 \ \ a_{x_2}=1 \ \ldots \ a_{x_n}=1\) ，其余为0

令数组 \(b\) 为 \(b_i = a_i \ xor \ a_{i-1}\)

操作是数组 \(a\) 对于 \([l,l+p-1]\) 异或 \(1\)

容易发现在数组 \(b\) 上，这个操作相当于对 \(b_{l-1} \ xor \ 1\)，\(b_{l+p-1} \ xor \ 1\)

也就是每次对数组 \(b\) 上相差为奇质数的下标取反

考虑最初的数组 \(b\) ，显然会有偶数个 \(1\)

可以感性的想一想，可以转化成每次通过几次操作删掉两个 \(1\)

（至于为什么可以这样想，lg讨论区有一个简短的证明）

于是，我们令 \(f(l,r)\) 表示删掉 \(l\) 和 \(r\) 上的 \(1\) 的最小操作次数

设 \(r-l = k\)

显然，当 \(k\) 是一个奇质数时，\(f(l,r)=1\)

接下来将 \(k\) 分为奇数和偶数考虑

若 \(k = 2\) ，可以通过两次操作完成，即将 \((l,l+7)\) 和 \((l+2,l+7)\) 取反

若 \(k = 4\) ，可以通过两次操作完成，即将 \((l,l+7)\) 和 \((l+4,l+7)\) 取反

若 \(k \geq 6\)

由于哥德巴赫定理，必有奇质数 \(p\)，\(q\) 满足 \(p+q=k\)

所以只需要将 \((l,l+p)\) 和 \((l+p,l+p+q)\) 取反即可

若 \(k = 1\) ，可以通过三次操作完成，即将 \((l,l+7)\) 和 \((l+4,l+7)\) 和 \((l+1,l+4)\) 取反

若 \(k \geq 9\)

先将 \((l,l+3)\) 取反，然后就变成了一个 \(k-3\) 的偶数情况

所以总共 \(3\) 次可以解决

总结一下：

当 \(k\) 为奇质数时，\(f(l,r)=1\)

当 \(k\) 为偶数时，\(f(l,r)=2\)

当 \(k\) 为奇合数时，\(f(l,r)=3\)

有一个比较显然的贪心策略，就是从代价为 \(1\) 的优先考虑，能删就删

（贪心正确性可以自己想一下，应该是比较简单的）

考虑差为奇质数的情况，由于差是奇数，所以两个位置的奇偶性不同，可以按奇偶性分类

我们对差为奇质数的两个点直接连边，这样就相当于求一个二分图的最大匹配

求完最大匹配后剩下来的一些点，奇偶性相同的点可以用第二种方法删

最后要么剩下一奇一偶，要么删完了

如果剩一奇一偶，那就在加 \(3\) 次操作

来源链接：https://www.cnblogs.com/kentsbk/p/18650933