首页 > 试题广场 >

非整除集合

[编程题]非整除集合
  • 热度指数: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

输出

3
先说一下例子里面的「19,22,25」是能被4整除的,应该是题目出错了!
思路很简单,直接求余数,假如按例子「10,10,12,19,22,24,25」看求4的余数可以知道:[2,2,0,3,2,0,1],统计起来就是2个0,1个1,3个2,1个3。
0这里,最多只能有一个,比如两个被4整除的数肯定加起来还能被4整除,接下来就是1和3了,这两个哪个多就选哪个,因为1和3任选一个加起来肯定就能被4整除,所以就选最多的那个,另一个不选。接下来就是最中间那个,这里就是2了,它也最多只能选1个,因为两个求余为2的加起来也能被4整除,所以这里特殊的就是0和中间那个,存在就加1,其他的是选两个里面最大的那个,代码如下:
import java.util.*;
 public class Main {
     public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        int [] array1=new int [n];
        for (int i = 0; i < m; i++) 
            array1[sc.nextInt()%n]++;
        int sum=array1[0]>0?1:0;
        for (int i = 1,j=n-1; i<=j; i++,j--) 
                sum+=(i==j)?(array1[i]>=1?1:0):Math.max(array1[i], array1[j]);
        System.out.println(sum);
     }    
    
发表于 2019-07-11 16:13:44 回复(9)
求出任意两个数不能被K整除的集合
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

vector<vector<int>>  q;
bool BT(vector<int> res,int k)
{
    for(unsigned int i=0;i<res.size();i++)
    {
       for(unsigned int j=i+1;j<res.size();j++)
       {
           if((res[i]+res[j])%k==0)
           return  false;
       }
    }
    return  true;
}

void DFS(vector<int> ret,vector<int>& res,int k)
{
   for(unsigned int i=0;i<ret.size();i++)
   {
      res.push_back(ret[i]);
      for(unsigned int j=i+1;j<ret.size();j++)
      {
       res.push_back(ret[j]);
       if(BT(res,k)) continue;
       else
         res.pop_back();
      }
      q.push_back(re***r />       re***r />    }
}

int main()
{
   int N,K,input;
   cin>>N>>K;
   vector<int>  ret,re***r />    while(cin>>input)
       ret.push_back(input);
   if(K==0) {cout<<ret.size();return 0;}
   DFS(ret,res,K);
   int m=0;
   for(int i=0;i<q.size();i++)
   {
      int t=q[i].size();
      m=max(m,t);
   }
   cout<<m<<endl;
    return 0;
}

发表于 2019-12-01 20:00:09 回复(0)
//K范围很小啊,直接求余数哈希,特别注意处理一下余数为0,以及K为偶数时余数为K/2的情况即可。
#include<iostream>
using namespace std;

int main() {
    int N, K;
    cin>>N>>K;
    
    int rec[K];
    long long tmp;
    int res = 0;
    
    for(int i = 0; i < K; i++) {
        rec[i] = 0;
    }
        
    for(int i = 0; i < N; i++) {
        cin>>tmp;
        rec[tmp%K]++;
    }
    
    if(rec[0] > 0) {
        res = 1;
    }
    if(K%2 == 0) {
        for(int i = 1; i <= K/2-1; i++) {
            res = res + max(rec[i], rec[K-i]);
        }
        if(rec[K/2] > 0) {
            res++;
        }
    }
    else {
        for(int i = 1; i <= K/2; i++) {
            res = res + max(rec[i], rec[K-i]);
        }
    }
    cout<<res<<endl;
    return 0;
}

发表于 2020-07-10 13:47:57 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k,x;
    cin>>n>>k;
    int a[k];
    memset(a,0,sizeof(a));
    for(int i=0;i<n;i++){
        cin>>x;
        a[x%k]++;
    }
    int s = a[0]>0?1:0;
    for(int i=1,j=k-1;i<=j;i++,j--)
        s += (i==j)?(a[i]>0?1:0):max(a[i],a[j]);
    cout<<s<<endl;
    return 0;
}

发表于 2019-11-18 12:54:44 回复(0)
eng写的,也能过就是
import java.util.*;
public class Main {
    // 子集合中任意两数之和不能被k整除
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt(), k = in.nextInt();
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = in.nextLong();
            }
            fun(arr, k);
        }
    }
    // 动态规划处理
    public static void fun(long[] arr, int k) {
        int n = arr.length;
        Node[] dp = new Node[n];
        for (int i = 0; i < n; i++) { // base case
            dp[i] = new Node();
            if (arr[i] % k != 0) {
                dp[i].size = 1;
                dp[i].list.add(arr[i]);
            }
        }
        int max = 0; // 最大长度
        for (int i = 1; i < n; i++) {
            int idx = -1; // 记录最大下标
            for (int j = 0; j < i; j++) {
                if ((arr[i] + arr[j]) % k != 0) { // 存在
                    boolean flag = true;
                    for (long l : dp[j].list) { // 观察每一个是否可行
                        if ((arr[i] + l) % k == 0) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) { // 都相安无事就更新
                        if (dp[j].size + 1 > dp[i].size) {
                            dp[i].size = dp[j].size + 1;
                            idx = j;
                        }
                    }
                }
            }
            if (idx != -1) { // 找到了可以加入的集合
                dp[i].size = dp[idx].size + 1;
                dp[i].list = dp[idx].list;
                dp[i].list.add(arr[i]);
                max = Math.max(max, dp[i].size);
            }
        }
        System.out.println(max);
    }
}
// 结点的定义
class Node {
    int size;
    ArrayList<Long> list;
    public Node() {
        size = 0;
        list = new ArrayList<>();
    }
}
发表于 2022-06-26 19:08:19 回复(0)
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)

package main
import (
	"fmt"
)
/*

1,感觉是这是一个数学问题,和数据结构没什么关系,开始是想用回溯组合求值,但是后来发现了其中的数学规律。
题目说 任意两个数字的和都不能被K整除, 也就是这两个任意数之和 对K模运算取余数 不能整除 K 。这里调一下计算顺序。,先取模,并记录次数。
1.1 将 N个数 对 K 取余 ,将余数和对应出现的次数放入 Map中。
1.2 [0, 1, 2, 3, .... , K-1] 是 Map 中可能存在的键值。将这些键值从中间分为两份,因为 中间堆成,比如 1 和 K-1 不能同时出现,哪一个出现的次数多就取哪一个
1.3 处理边界条件, K 为 偶数, K/2 最多能出现依次, K为奇数,比较 K/2 和 K-K/2 那个次数出现的多。
1.4 还有一个边界条件,0 最多出现一次
*/
var SMap map[int]int
func main(){
	var N,K, t int
	fmt.Scanf("%d",&N)
	fmt.Scanf("%d",&K)
	SMap := make(map[int]int)

	for i:=0;i<N;i++{
		fmt.Scanf("%d",&t)
		SMap[t%K] = SMap[t%K]+1
	}
	sum := 0
	if SMap[0] > 0 { // 边界为 0 的情况,最多只能出现一次
		sum = 1
	}
	for i := 1; i < K/2 ; i++ {
		sum += Max(SMap[i], SMap[K-i]) // 对称比较, i 和 K-i 不能同时现在结果中。
	}
	if K%2 == 0 {  // 边界条件, 处理 K 的奇偶情况
		if SMap[K/2] > 0 { // K/2 = K-K/2
			sum += 1
		}
	} else {
		sum += Max(SMap[K/2], SMap[K-K/2]) // K/2 != K-K/2
	}
	fmt.Println(sum)
}
func Max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

编辑于 2020-07-26 17:01:45 回复(0)
看到题解用求余的方法,这里分享另外一种思路;
1. 输入数组;
2. 从数组的第一个索引开始判断;
3. 判断该值和前面的数组值是否相加能被整除,若能被整除,则该值不能加入进去;若不会被整除,则可以加入进来,num++;
此时,此方法只能做到ac80%的正确率。原因是,步骤3中,之前以前被明确不能加入的值,下一次可以加入。
 所以加入int unpeek_visited[1000] = {0};来辅助判断。
作者:牛客487907932号
链接:https://www.nowcoder.com/questionTerminal/361ff5dd893c4e11856735e52007fca7?toCommentId=6317087&ran=152
来源:牛客网
#include<vector>
#include<algorithm>
using namespace std;
int N, K;
int unpeek_visited[1000] = {0};
int judge_it(vector<int> S, int must_i)
{
    int i;
    for(i=0; i<must_i; i++)
    {
        if((S[i]+S[must_i])%K == 0 && unpeek_visited[i]!=1)
        {
            unpeek_visited[must_i] = 1;
            //printf("111must_i:%d %d\n", S[i], S[must_i]);
            return 1;
        }
    }
    
    //printf("000must_i:%d %d\n", S[i], S[must_i]);
    return 0;
}
int main()
{
    cin >> N;
    cin >> K;
    
    vector<int> S;
    int i=0;
    for(i=0; i<N; i++)
    {
        int temp;
        cin >> temp;
        S.push_back(temp);
    }
    int rt_max = 0;;
    for(i=0; i<N; i++)
    {
        if(judge_it(S, i) == 0)
        {
            rt_max++;
        }
            
    }
    
    cout<<rt_max;
    
}
编辑于 2020-06-16 13:15:03 回复(1)
80%,是什么问题??
def solve(nums, n, k):
    numcnt = [0 for i in range(k)]
    for num in nums:
        numcnt[num % k] += 1
    
    count = 0
    count += min(1, numcnt[0])          # 0
    if k & 0x01:    # 奇数
        for i in range(1, k // 2 + 1):
            count += max(numcnt[i], numcnt[k - i])
    else:           # 偶数
        count += min(1, numcnt[k // 2]) # k / 2
        for i in range(1, k // 2):
            count += max(numcnt[i], numcnt[k - i])
    return count

getNumsFromString = lambda x: list(map(int, x.strip().split()))
n, k = getNumsFromString(input())
nums = getNumsFromString(input())
print(solve(nums, n, k))


发表于 2020-06-05 20:59:51 回复(0)
class Solution {
    public:
        long hanWuJi_JiHeYuanSuBuNengZhengchu(vector<int> S, int K)
	{
		for (auto iteri = S.begin(); iteri != S.end(); iteri++)
		{
			for (auto iterj = iteri+1; iterj != S.end(); )
			{
				if ((*iteri + *iterj) % K == 0)
				{
					iterj=S.erase(iterj);
				}
				else iterj++;
			}
		}
		return S.size();
	}
};

发表于 2019-09-08 14:37:37 回复(0)
## 为啥只能过80%???
N, K = list(map(int, input().split()))
nums = list(map(int, input().split()))

arr = [0 for _ in range(K)]
for it in nums:
    arr[it%K] += 1
    
tSum = 0
if arr[0] >= 1:
    tSum = 1

i, j = 1, K-1
while i <= j:
    if i == j and arr[i] >= 1:
        tSum += 1
    else:
        tSum += max(arr[i], arr[j])
    i+=1
    j-=1
    
print(tSum)

发表于 2019-08-23 14:59:20 回复(0)
#include<iostream>
using namespace std;
int main()
{
	int n,k,a[10001],i,num[101]={0},ke,max=0;
	cin>>n>>k;
	for(i=1;i<=n;i++){cin>>a[i];a[i]=a[i]%k;num[a[i]]++;}//取余数,统计一下
	if(k%2==0){ke=k/2-1;if(num[k/2])max=1;}//k/2是整数的话处理一下
	else ke=k/2;
    if(num[0])max++;//余数为0的只能有一个
	for(i=1;i<=ke;i++)
	if(num[i]>num[k-i])max=max+num[i];
	else max=max+num[k-i];//i和k-i哪个多就加哪个
	cout<<max;
	return 0;
}

发表于 2019-08-19 23:37:10 回复(0)
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)
发现Python和MATLAB代码都没办法提交
MATLAB:
S_and_K_real = input('Please input the length of S and K:');
S_real = input('Please input S:');
S_length = S_and_K_real(1);
K = S_and_K_real(2);
tmp = ones(S_length,1);
matrix1 = tmp*S_real;
matrix2 = matrix1';
matrix_final = matrix1 + matrix2;
matrix_mod = mod(matrix_final,K);
max_length = 1;
for i=1:S_length
    matrix_mod_lines = matrix_mod(i,:);
    tmp_length = find(matrix_mod_lines == 0);
    if tmp_length > max_length
        max_length = tmp_length;
    end
end
fprintf('The longest length of S- is:%d',max_length)
Python:
import numpy as np
S_and_K = input('Please input the length of S and K:')
S = input('Please input S:')
S_and_K_real = np.array(S_and_K.split(' '),dtype = np.int);
S_length = S_and_K_real[0]
K = S_and_K_real[1]
S_real = np.array(S.split(' '),dtype = np.int)
tmp = np.ones([S_length,1],dtype = np.int)
matrix1 = tmp*S_real
matrix2 = matrix1.T
matrix_final = matrix1 + matrix2
matrix_mod = np.mod(matrix_final,K)
max_length = 1
for i in range(S_length):
  matrix_mod_lines = matrix_mod[i,:]
  tmp_length = S_length-len(np.flatnonzero(matrix_mod_lines))
  if tmp_length > max_length:
    max_length = tmp_length
   
print('The longest length of S- is:',max_length)
发表于 2019-06-28 21:06:33 回复(0)