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

Question

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

Answer 1

首先计算所有的集合元素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 进行排序。