ARC080D Prime Flip

题意：有无限枚硬币，其中有 枚硬币 初始时正面朝上，其余均为背面朝上。

每次可以选择一段区间 ，将区间内所有硬币翻转，其中 为奇质数。

问最少多少次操作能使得所有硬币全部为背面朝上。可以证明一定有解。

，，时限 。

---

先将原序列差分，问题变为可以在两个差为奇质数的位置 ，多少次能使得整个序列变为全 。

考虑将 成对解决。对于两个位置 :

• 若 为奇质数： 次操作。

• 若 为偶数：由哥德巴赫猜想， 次操作。

• 若 为奇合数：先随便整一个质数，然后转化为偶数的情况， 次操作。

（不难发现 有偶数个，故一定有解）

于是，问题就被转化为了特殊的一般图最大权匹配。

由于权值的特殊性，可以贪心。

先尽量添加价值为 的匹配，这似乎也是一个一般图最大匹配，不过由于位置的差值是奇（质）数，可以黑白染色变为二分图匹配。

（若拆掉一个价值为 的匹配，利用剩余的 边只会得到更劣的方案）

将被匹配掉的点取出。剩余的图中，也可以贪心地添加价值为 的匹配。

将所有点按照奇偶性分为两部分，每一部分内部都充满了 边，尽量配对即可。

使用 Dinic 求解二分图匹配，复杂度 。