简介
大概就是一些利用随机，但是正确率非常高的算法
例题
简要题意：给定 $n$ 个整数 $a_i$，求一个最打的集合满足存在一个 $m\ge 2$，且这个集合中的数模 $m$ 同余
$n\le 2\times 10^5,a_i\le 4 \times 10^{12}$
简要题解：我们取 $m=2$，容易得到答案大于等于 $\frac n 2$
那么我们现在考虑随机两个数 $a[x]$ 和 $a[y]$，那么这两个数在最终答案的集合的概率是 $\frac 1 4$
我们不妨假设这两个数在最终集合中，那么 $m$ 一定是 $a[x]-a[y]$ 的质因子，$m$ 只有最多 $11$ 个
因为每次成功的概率只有 $\frac 1 4$，所以我们需要多枚举几次，大概 $40$ 次左右即可，这个时候不正确的概率只有 $(\frac{3}{4})^{40}$，已经足够小了，时间复杂度 $O(40\sqrt a_i+11n)$