题意简述： 给定 个数的数组 （），从中选出不相交且互质的两对数或输出无解。
首先不难想出一个 的解法，那就是枚举每对数尝试找到一组解。但是你注意到一个数需要花 的时间来枚举，如果没找到一组解这个时间就是十分浪费的。
考虑如何快速判断在数组里一个数是否在数组里有与其互质的数，有的话再枚举。这样最多只要枚举 遍。考虑将原问题强化，计算一个数在数组里与其互质的数的个数。
我们又注意到前 个质数的乘积 因此对于 ， 的质因数个数不会超过 个。显然两个数互质当且仅当两个数没有共同的质因数，因此我们要求的是数组中不整除 的任何一个质因数的数，而至少整除某些质数的数的个数是好求的。此时可以考虑使用容斥原理。
记 表示整除集合 中所有质数的数的个数，即满足 的 的个数， 为 的质因数集合。那么数组中不整除 的任何一个质因数的数的个数就是
至此，而我们就可以快速判断一个数在数组中是否有与其互质的数。这部分算法的复杂度是 ， 表示 的质因数个数。但是如果想这样随便找两个存在与其互质的数枚举的话仍然会挂，可以看下第一个样例 ，如果你选了 和 ，那么剩下的 和 并不互质。
此时我们有一个简单的贪心，就是先选出一个存在与其互质的数的数 ，然后从与 互质的每个数 中，找到在数组中与 互质的数最小的一个 ，将 配对并从原数组中删去。这个贪心的想法就是与数组中更多数互质的数有着更多的选择，在选走两个数之后更有可能保留了几个数与其互质。接下来我们考虑严格证明这个贪心的正确性。
将原问题建模，将互质的两个数连边。我们的问题就是求出一个大小为 的匹配。我们上面求出来的与一个数互质的数的个数就是一个点的度数。我们希望证明，在删掉这对点之后，如果不存在一个大小为 匹配（也就是剩下的点之间没有连边），那么原图没有大小为 的匹配。由于剩下的点没有连边，显然原图中这些点只能和 连边，因此剩下的点在原图中度数为 或 。
- 如果剩下的点度数为 ，假设存在一个点与 连边，与 相连的点的最小度数就是 ，因此 的度数也是 ，因此所有其它点都和 连边，否则所有其它的点都和 连边。这种情况下整张图是一张菊花图，显然不存在大小为 的匹配。
- 假设存在至少一个剩下的点度数为 ，那么这个点必须和 同时连边。同时因为这个点点数为 ，因此 的度数小于等于 。另一方面， 已经和 以及这个点连边了，因此 的度数为 。又因为 的度数是与 相连的点中最小的，因此不可能有其他的点连接到 或 。此时图是一张三元环，显然也不存在大小为 的匹配。
因此这个贪心是正确的。这部分的复杂度就是线性的。
参考代码被放在了洛谷剪切板。如果你访问不了这个链接，可以试试这个。