【校内模拟】互异

这道题暴力分比较高

将m从1开始枚举,对m取模后判断有多少个重复得数,若<=k,就输出m

然而看了题解以后,简直是MMP 我学到了很多

枚举还(^{TM})能剪枝!

两个数模m后不相等,等价于两个数的差不是m的倍数。所以我们先计算出n个数的两两之差,

用线性筛质数做一个粗略的预处理,得到 b 数组,b[i]表示这 n*(n-1)/2 个差中至少有b[i]个含有因子i(因为是粗略估计,所以用了“至少”)。

然后我们从小到大枚举m,在枚举时首先判断b[m]是否大于k*(k+1)/2,如果是,则去掉k个数依然不满足条件,那么将m加一

否则暴力判断

原文地址:https://www.cnblogs.com/yjkhhh/p/9815100.html