2023.8.24 LGJ Round-526互联

A

有 \(n(n\le 750)\) 个正整数 \((a_i\le 10^9)\)，你需要删除一些数，使得剩下的数两两加起来都不为质数。

若 \(a_i+a_j\in \text{prime}\)（这里使用 Miller-Rabin 即可），将 \(i\) 和 \(j\) 连边。
我们就是要求一个最大独立集。
一般图是求最大独立集是 NP 问题。但是我们发现去掉所有 \(a_i=1\) 到只剩一个后，原图是二分图。
奇数在一边，偶数在一边，我们求二分图最大独立集=点数-最大匹配。

Round