python中不可分的子集

Question

我给了一个n个整数的集合S,并且必须打印S的最大子集S'的大小,其中S'中任何2个数字的总和不能被k整除.

输入格式

第一行包含2个以空格分隔的整数,分别为n和k.第二行包含n个以空格分隔的整数,用于描述集合的唯一值.

我的代码:

import sys


n,k = raw_input().strip().split(' ')
n,k = [int(n),int(k)]
a = map(int,raw_input().strip().split(' '))
count = 0


for i in range(len(a)):
    for j in range(len(a)):
        if (a[i]+a[j])%k != 0:
            count = count+1

print count

输入:

4 3
1 7 2 4

预期产出:

3

我的输出:

10

我究竟做错了什么？任何人？

Answer 1

您可以O(n)使用以下方法及时解决:

L = [0]*k

for x in a: 
    L[x % k] += 1
res = 0
for i in range(k//2+1):
    if i == 0 or k == i*2:
        res += bool(L[i])
    else:
        res += max(L[i], L[k-i])

print(res)