Codeforces Round #748 All are Same/Half of Same 题解 (Java/C++)

题解

D1. All are Same

首先，如果所有数都一样，那么k可以是任意值。所以我们只需要考虑存在不同的值的情况。

因为通过减去若干次k后可以得到相同的数。所以一定可以在减去若干次k之后得到数组中最小的那个数。

于是我们考虑数组中每个数与数组中最小值的差。然后求最大公约数即可（0除外）。

D2. Half of Same

有了D1的结论，D2就被转变为如下问题：找到尽可能大的k，对于至少一半的数按照D1的方法计算最大公约数的结果为k。

但是显然，如果我们$C_{40}^{20}$的枚举这一半的数的话显然是会TLE的。

我们注意到在D1的做法中，我们需要利用数组中最小值作为基准，然后再计算最大公约数。而对于D2，根据选择的数不同，这个最小值也不同。
于是我们想到枚举最小值，因为n只有40。

现在我们的问题就变成了在给定一个最小值的情况下，选出至少$\frac n 2 -1$个数，使得其最大公约数尽可能大。
但是如果通过辗转相除法来计算最大公约数需要提前知道这些数有哪些，同时为了知道这些数有哪些就会涉及到枚举。
因此，我们直接统计出每个数的所有因数。如果一个因数出现次数大于$\frac n 2$，那么这个因数就是可能的k。

所以具体做法是：