非整除集合

[编程题]非整除集合

热度指数：2732 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个由正整数组成的集合S，找出一个最大的子集合S，使得S中任意两个数字的和都不能被K整除。

例如S=「10，10，12，19，22，24，25」，K=4。此时S最多只能取3个数，可能的取值为「10，12，25」或者「19，22，24」等。

输入描述:

输入为两行，第一行两个数字，分别表示集合S的元素数量N和K。第二行为N个数字，分别是S的各个元素值。


数据范围：
1 < N < 10^5
1 < K < 100
1 < S[i] < 10^9

输出描述:

输出为一个数字，集合S的最大长度。

示例1

输入

4 3
1 7 2 4

输出

算法知识视频讲解

Python

牛客758087690号

a=list(map(int,input().split()))
if len(a)<2:
    l=a
    k=int(input())
else:
    l=a[0]
    k=a[1]
arr=list(map(int,input().split()))
arr_1=[i%k for i in arr]
count_n=0
for i in range(0,k):
    if i in arr_1:
        if i==0:
            count_n+=1
        elif i ==k/2:
            count_n+=1
        else:
            num_i=0
            for j in arr_1:
                if j==i:
                    num_i+=1
            if k-i in arr_1:
                num_k_i=0
                for p in arr_1:
                    if p==k-i:
                        num_k_i+=1
                count_n+=max(num_i,num_k_i)
                arr_1.remove(k-i)
            else:
                count_n+=num_i
        arr_1.remove(i)
print(count_n)

发表于 2021-03-27 00:19:46 回复(0)

Python

白色纯度

80%的通过率，找不到错在哪里。

def long_set(num,k):
    if not num:
        return 0
    if k==1 or len(num)==1:
        return 1
    dic = {}
    for i in num:
        tem = i%k
        dic[tem] = dic.get(tem,0)+1
    dp = [0 for _ in range(k)]
    for i in list(dic.items()):
        dp[i[0]] = i[1]
    res = min(1,dp[0])
    if k&1==1:
        j = 1
        while j <= k//2:
            res += max(dp[j],dp[k-j])
            j += 1
    else:
        m = 1
        while m<k//2:
            res += max(dp[m],dp[k-m])
            m += 1
        res += min(1,dp[m])
    return res
if __name__=='__main__':
    n,k = list(map(int,input().split()))
    num = list(map(int,input().split()))
    print(long_set(num,k))

发表于 2019-08-12 10:15:18 回复(0)