c++ - 不能被 K 整除的两个和的最大子集

给定集合 {1, 2, 3, ... ,N}。我必须找到给定集合的子集的最大大小，以便子集中的任何 2 个数字的总和不能被给定的数字 K 整除。N 和 K 可以达到 2*10^9，所以我需要一个非常快的算法。我只想出了一个复杂度为 O(K) 的算法，它很慢。

---

Best Answer-推荐答案

首先计算所有的集合元素 mod k。然后解决简单的问题: 找到给定集合的子集的最大大小，使得子集中任意 2 个数字的总和不等于给定数字 K。 我将此集合分为两组(i和k-i)，您不能同时选择set(i)和set(k-i)。

int myset[]
int modclass[k]

for(int i=0; i< size of myset ;i++)
{
    modclass[(myset[i] mod k)] ++;
}

选择

for(int i=0; i< k/2 ;i++)
{ 
    if (modclass[i] > modclass[k-i])
    {
        choose all of the set elements that the element mod k equal i
    }
    else
    {
        choose all of the set elements that the element mod k equal k-i
    }
}

最后，您可以从元素 mod k 等于 0 或 k/2 中添加一个元素。

这个解决方案的算法复杂度为 O(K)。

你可以用动态数组来改进这个想法:

for(int i=0; i< size of myset ;i++)
{
    x= myset[i] mod k;
    set=false;
    for(int j=0; j< size of newset ;j++)
    {
        if(newset[j][1]==x or newset[j][2]==x)
        {
            if (x < k/2)
            {
                newset[j][1]++;
                set=true;
            }
            else
            {
                newset[j][2]++;
                set=true;
            }
        }
    }
    if(set==false)
    {
        if (x < k/2)
        {
            newset.add(1,0);
        }
        else
        {
            newset.add(0,1);
        }
    }
}

现在您可以选择复杂度为 O(myset.count) 的算法。您的算法比 O(myset.count) 还多，因为您需要 O(myset.count) 来读取您的集合。 该解决方案的复杂度为 O(myset.count^2)，您可以根据输入选择算法。比较 O(myset.count^2) 和 o(k)。 为了获得更好的解决方案，您可以根据 mod k 对 myset 进行排序。

关于c++ - 不能被 K 整除的两个和的最大子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14001634/