非正解做法，但大概率正确（实际上过不了 Hack）。
套路的，考虑让每个 \(a_i\) 减去整体的平均值，问题转换为让两个集合的和均为 \(0\)。
我们每次随机打乱 \(a\) 数组，并贪心的将其插入两个堆中，最后判断即可。
由于同余的性质可得，如果 \(a_x\equiv a_y \pmod p\)，则 \(|a_x-a_y|\bmod p=0\)。
所以我们随机选择 \(2\) 个 \(a_i,a_j(i\ne j)\) 的话，由于答案集合大于 \(2\)，记 \(d=|a_i-a_j|\)，则 \(m|d\) 的概率是 \(\dfrac{1}{4}\)。
由这个性质直接做即可。
由于要求数量超过一半，因此可以考虑随机化，每次有 \(\dfrac{1}{2}\) 的概率正确。
具体实现时，先将随机的数的因数存下来，记为 \(d_i\)。
记 \(m_i=\gcd(a_i,x)\)，则 \(pos_i\) 为 \(\min_i(m_i\le d_i)\)，令 \(cnt_i\) 为 \(i\) 在 \(\gcd\) 中的出现次数，初始时 \(cnt_{pos_i}=1\),（这一过程类似离散化），\(cnt_i=\sum_{d_i|d_j}cnt_j\)，直接转移即可。
我们取阈值 \(w=10\)，错误概率为 \(2^{-10}\)。
考虑贪心，和第一题思路类似，维护两个堆。
我们每次考虑如下选择：
- 加入第 \(1\) 堆后，\(a_i\) 对 \(\gcd\) 不产生任何影响，则将其放入第 \(2\) 堆。
- 否则将其放入第 \(1\) 堆。
这样显然是可以被卡的。
我们可以多做几次，随机排列 \(a_i\)，正确性提升。
发现随机选择 \(x,y,z\)，实际上答案为根节点的左右儿子概率最大，记为 \(u,v\)。
则可以通过 \(n\) 次询问 \((u,v,i)\) 得出根的值。
标签：cnt,Code,gcd,随机化,概率,随机 From： https://www.cnblogs.com/WhisperingWillow/p/18193632