首页 > 试题广场 >

k倍多重正整数集合

[编程题]k倍多重正整数集合
  • 热度指数:1407 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

k倍多重正整数集合的定义是:在一个多重集合(元素可以重复)中,不存在一个正整数是另一个正整数的k倍。

现在小Mn个正整数,你可以选择其中一些数构成k倍多重正整数集合。请求出最多能选出多少数来构成它。


输入描述:
第一行有两个整数n, k(1 <= n <= 10^5, 1 <= k <= 10^9)。

接下来一行有n个正整数a1, a2, ..., an (1 <= ai <= 10^9)。


输出描述:
最多能选出多少数构成k倍多重正整数集合。
示例1

输入

6 2
2 3 6 5 4 10

输出

3

说明

第一个样例中,我们选择2,3,5即可满足要求,因为k == 2,不存在一个数是另一个数的两倍。
示例2

输入

2 2
2 2

输出

2

说明

第二个样例中,我们选择2,2即可满足要求,因为k == 2,2也不是2的两倍,注意多重集合元素可以重复。
头像 牛客题解官
发表于 2020-06-05 18:50:38
题解:题目难度:三星 考察点: 哈希,思维 易错点: 很多同学在枚举倍数的时候会漏掉当的值为的情况,事实上,这种情况需要单独讨论,的值为1时,集合最大可容纳的元素个数就是集合中元素的种数,也就是让集合中不同的元素只能出现1次。 题解: 这题的数据范围为,因此如果对于每个位置暴力去探寻它的倍是否存在与 展开全文