我给定集合{1，2，3，...，N}。 我必须找到给定集合的子集的最大尺寸，使得从子集中的任何2数的总和不整除给定数目K. N和K可以是高达2×10 ^ 9，所以我需要一个非常快的算法。 我只是想出了复杂度为O的算法（K），这是缓慢的。
Answer 1:
第一计算所有元素集合的模k.and解决简单的问题：查找给定集合的子集的最大尺寸，使得从子集中的任何2数之和是不是由给定数目K.我除以该组等于二套（i和KI），你不能选择设置（i）及设定（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
}
}
最后可以从添加一个元素的元素模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），你可以选择算法取决于你input.with O（myset.count ^ 2）和O（K）之间的比较。 并为更好的解决方案，你可以排序MYSET基于模km。
Answer 2:
我假设一组数字始终是1至N一段N.
考虑第一N-（N模K）的数字。 K个连续数的形式地板（N / K）的序列，以减少模k从0到K-1。 对于每个组，地板（K / 2）必须被丢弃用于具有减少模k是地板的另一子集（K / 2）的否定模k。 您可以从每组K个连续号码的保持天花板（K / 2）。
现在考虑剩下的N模的K个数字。 他们削减国防部K开始在1.我还没有制定出确切的限制，但如果N模K小于约K / 2，你将能够让所有的人。 如果没有，你将能够保持对他们的第一顶部（K / 2）。
================================================== ========================
我相信这里的理念是正确的，但我还没有制定出所有细节。
================================================== ========================
这是我的问题和答案的分析。 在接下来| X | 是地板（X）。 该解决方案是一个类似于在@康斯坦丁的答案，但在少数情况下是不同的。
首先考虑的K * | N / K | 元素。 它们包括| N / K | 的削减的重复模K.
在一般情况下，我们可以包括| N / K | 这k个模ķ受到以下限制元素：
如果（K + K）％K是零，我们可以仅包括一个元件，其为k模K.即对于k = 0和k =（K / 2）％K的情况下，这只能发生甚至K.
这意味着，我们得到| N / K | * |（K-1）/ 2 | 从重复的元件。
我们需要纠正被省略的元素。 如果N> = K我们需要添加1为0模K个元素。 如果k是偶数和N> = K / 2，我们还需要添加1所述的（K / 2）％K中的元素。
！最后，如果M（N）= 0，我们需要添加的重复元件的部分或完整拷贝，分钟（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.例如某些情况下的版本，考虑N = 4，K = 6。 正确答案是3，集合{1，2，3}的大小。 @康斯坦丁的公式给出|（6-1）/ 2 | = | 5/2 | = 2上面的公式从最后一行得0对于每个前两行的，1从第三行，和图2，给出了正确的答案。
Answer 3:
计算公式为
|N/K| * |(K-1)/2| + ost
ost =
if n<k:
ost =0
else if n%k ==0 :
ost =1
else if n%k < |(K-1)/2| :
ost = n%k
else:
ost = |(K-1)/2|
其中，| A / B | 例如| 9/2 | = 4 | 7/2 | = 3
例如，n = 30，K = 7;
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
1 2 3 | 4 | 5 6 7 - 是第一行。 8 9 10 | 11 | 12 13 14 - 第二行，如果我们在每一行获取第一数3我们可以得到该子集的大小。 我们也可以从将一个数字（7 14 28）
获取第一数3（1 2 3）的数|（K-1）/ 2 | 。 许多这行是| N / K | 。 如果没有残留，我们可以添加一个号码（例如最后一个数字）。 如果残余物<|（K-1）/ 2 | 我们得到的其他最后一行的所有数量越来越|（K-1）/ 2 |。
感谢例外情况。 OST = 0如果k>Ñ
Answer 4:
n,k=(raw_input().split(' '))
n=int(n)
k=int(k)
l=[0 for x in range(k)]
d=[int(x) for x in raw_input().split(' ')]
flag=0
for x in d:
l[x%k]=l[x%k]+1
sum=0
if l[0]!=0:
sum+=1
if (k%2==0):
sum+=1
if k==1:
print 1
elif k==2:
print 2
else:
i=1
j=k-1
while i<j:
sum=sum+(l[i] if l[i]>=l[j] else l[j])
i=i+1
j=j-1
print sum
Answer 5:
这是解释阿布拉TYAGI和阿明K公司的解决方案。
该解决方案的做法是：
- 创建具有K桶和所有组从输入数组d的元素到K个桶阵列升。 每个桶L [I]含有D的元件，使得（元素％K）= I。
- 所有由K分别独立地分割所述元件是在L [0]。 因此，只有这些要素（如果有的话）的人可以在我们的最终（最大）子集的归属。 这些元件中的任何两个的总和是整除K.
- 如果我们以L添加从L [I]的元素的元素[基]然后总和为K.整除。因此，我们可以从只有这些桶以我们的最后一组中的一个添加元素。 我们挑了最大的桶。
代码：d是包含初始集合大小为n的号码的数组。 这段代码的目标是找到d的最大子集的数量，使得没有两个整数的总和为2整除。
升是将包含ķ整数的数组。 这样做是为了减小每个（元件）的阵列d至（元素％k）和保存其出现的频率在阵列升。
例如，L [1]包含所有元素％K = 1的频率
我们知道，1 +（K-1）％K = 0，从而任一升[1]或L [K-1]必须被丢弃，以满足任何两个数字％k的总和应为0的标准。
但是，当我们需要d的最大的子集，我们选择L的较大[1]和L [K-1]
我们循环阵列升，使得对于（I = 1; I <= K / 2 && I <き;我++），然后执行上述步骤。
有两个异常值。 任何两个数的在升之和[0]组％K = 0。因此，添加1如果L [0]是非零的。
如果k是偶数，则循环不处理I = K / 2，并且由一个使用相同的逻辑与上述增量计数。
文章来源: Maximum subset which has no sum of two divisible by K
