ARC080F Prime Flip

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

\(N \le 100,x_i \le 10^7\)

网络流 筛法

校内模拟赛搬的题目，当时出成了 \(N \le 5000\)，\(x_i\) 随机。

首先将问题转化为差分形式，我们最后就是将所有数两两匹配，然后匹配的边权就是至少用多少个奇质数表示（和、差的形式）出这两个点的差值。

然后注意到边权为：

• 当两个点差值为奇质数的时候，就是 \(1\)。
• 如果为差值偶数，就是 \(2\)（这个可以直接打表证明）
• 差值为奇合数，那么就是 \(3\)。

这个时候我们发现，应该尽量选择 \(1, 2\) 长度的边，于是将所有数直接奇偶分组，然后就是二分图的最大匹配问题了！

但是我太懒了，在想到奇偶分组就直接想到了随机化，然后就是讲所有数 shuffle 一下，进行贪心的随机匹配，再加个卡时函数，发现正确率高的惊人！

然后就过了。

还有更加离谱的，这个还能过 ATC 的数据，随机过 ATC 3000*。

然后成为了最裂解

??