AtCoder Regular Contest 080 F - Prime Flip

题意

给你一个数轴，然后数轴上面每个位置都有一枚硬币。
一开始硬币处于正面。然后现在有n个位置的硬币被翻成反面。
你现在可以选择一个奇质数$p$p，然后把某个位置$i$i到$i+p-1$i+p−1之间所有的硬币都翻一遍。
问最少翻多少遍可以把所有硬币翻成正面。

思考历程

看到就想到哥德巴赫猜想了。
结果想了半天都没有什么好的策略。

题解

其实多加个差分就没了。我好菜啊。
我们设一个数$f[i]$f[i]表示当前第$i$i个数和第$i-1$i−1个数是否相同。若相同则为0，否则为1。
那么现在的目标就是把$f$f数组变成0.
而原来的操作也变成了选择一个奇质数，然后把奇质数两个头给$xor\ 1$xor 1

那么我们就分成三类讨论：

• 1、若现在有两个点的距离是奇质数（j-i），那么只需要一步就可以把这两个点给消掉。
• 2、若现在有两个点的距离是偶数，那么只需要两步就可以把这两个点给消掉。原因就是可以哥德巴赫猜想（距离为2或4的可以用5,3和7,3来弄掉）。
• 3、若现在有有两个点的距离是奇合数，那么需要三步就可以把这两个点给消掉。先消一个质数，然后再哥德巴赫。

于是我们可以开始匈牙利匹配了，贪心选情况即可，尽量选第一种情况。

口胡真开心。

代码

不想填了怎么办