【gcd】【桶】【伪暴力】欠扁的CD-白红宇的个人博客

【gcd】【桶】【伪暴力】欠扁的CD

发布日期：2021-05-07 22:46:25 浏览次数：21 分类：精选文章

本文共 491 字，大约阅读时间需要 1 分钟。

暴力枚举GCD然后统计倍数个数的方法

暴力枚举GCD然后统计倍数个数的方法，这种方法虽然看起来有点笨拙，但在某些情况下却是可行的。具体来说，我们可以通过以下步骤来实现：首先，遍历所有可能的GCD候选值，从最大的数开始往下枚举，然后检查这个GCD的倍数是否满足条件。

在这个问题中，我们需要找到一个最小的GCD，使得它的倍数个数达到或超过给定的阈值k。为了实现这一点，我们可以使用一个桶（数组）来统计每个数出现的次数。具体来说，我们可以创建一个数组t，其中t[x]表示数值x出现的次数。

步骤如下：

遍历所有数值，将它们存储在数组a中，并记录最大的数值maxx。

创建一个桶t，用于统计每个数值出现的次数。

从maxx开始，向下枚举每一个可能的GCD候选值i。

对于每一个候选值i，遍历它的倍数。具体来说，从i开始，每次增加i，直到超过maxx。

对于每一个倍数j，累加t[j]到一个计数器lj中。

如果lj达到或超过k，则输出当前的GCD候选值i乘以k，表示满足条件的最小GCD。

这种方法虽然简单，但在最坏情况下时间复杂度较高。因此，在实际应用中，需要根据具体需求选择合适的算法。

上一篇：【DP】送你一颗圣诞树

下一篇：【二分答案】工资

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！