最大子集,其中没有两个可被K整除的和

Question

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

Answer 1

首先计算所有设置元素mod k并解决简单问题:找到给定集合子集的最大大小,使得子集中任意2个数字的总和不等于给定数量K.我除以此集合到两组(i和ki)你不能同时选择set(i)和set(ki).

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进行排序.

Answer 2

我假设对于某些 N，这组数字始终是 1 到 N。

考虑前 N-(N mod K) 个数字。形成由 K 个连续数字组成的 Floor(N/K) 序列，并从 0 到 K-1 对 mod K 进行归约。对于每个组，必须删除floor(K/2)，以获得一个约简mod K，该约简mod K 是floor(K/2) 的另一个子集的否定mod K。您可以从每组 K 个连续数字中保留上限（K/2）。

现在考虑剩余的 N mod K 个数。它们从 1 开始减少 mod K。我还没有计算出确切的限制，但如果 N mod K 小于大约 K/2，您将能够保留所有它们。如果没有，您将能够保留其中的第一个上限（K/2）。

=================================================== =======================

我相信这里的概念是正确的，但我还没有弄清楚所有细节。

=================================================== =======================

以下是我对问题的分析和解答。接下来|x| 是楼层(x)。此解决方案与@Constantine 的答案中的解决方案类似，但在某些情况下有所不同。

考虑第一个 K*|N/K| 元素。它们由 |N/K| 组成 重复以 K 为模的缩减。

一般来说，我们可以包括|N/K| k 模 K 的元素受到以下限制：

如果 (k+k)%K 为零，我们只能包含一个 k 模 K 的元素。这就是 k=0 和 k=(K/2)%K 的情况，这种情况只能发生在偶数 K 的情况下。

这意味着我们得到 |N/K| * |(K-1)/2| 来自重复的元素。

我们需要纠正遗漏的元素。如果 N >= K，我们需要为 0 mod K 元素加 1。如果 K 是偶数且 N>=K/2，我们还需要为 (K/2)%K 元素加 1。

最后，如果 M(N)!=0，我们需要添加重复元素的部分或完整副本 min(N%K,|(K-1)/2|)。

最终公式为：

|N/K| * |(K-1)/2| +
(N>=K ? 1 : 0) +
((N>=K/2 && (K%2)==0) ? 1 : 0) +
min(N%K,|(K-1)/2|)

在某些甚至涉及 K 的情况下，这与 @Constantine 的版本不同。例如，考虑 N=4，K=6。正确答案是 3，即集合 {1, 2, 3} 的大小。@Constantine 的公式给出 |(6-1)/2| =|5/2| = 2. 上述公式的前两行分别为 0，第三行为 1，最后一行为 2，给出了正确答案。