首页 > 试题广场 >

非整除集合

[编程题]非整除集合

给定一个由正整数组成的集合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

算法知识视频讲解

bandiaoz

发表于 2024-12-27 02:18:54

解题思路题目要求找出一个最大的子集，使得其中任意两个数的和都不能被整除。关键发现：如果两个数的和能被整除，那么它们对的余数之和也能被整除对于余数为的数，最多只能选一个对于余数为的数（当为偶数时），最多只能选一个对于其他余数，要在和中选择数量较多的那组展开全文

VickW

发表于 2020-02-12 17:00:53

#include <iostream> #include <cstdio> using namespace std; int main(){ int n; //元素数量 int k; //任意俩个数不能被k整除 cin>>n>>k; 展开全文

C++工程师贪心数组 2019 寒武纪数学 Java工程师

来自：寒武纪2019秋招软件...

上传者：小小

难度：

14条回答 31收藏 8364浏览

查看代码

非整除集合

扫一扫，把题目装进口袋