11407: 【原1407】乐乐与果子
题目
题目描述
author: abcdabcd987 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1407
Description
乐乐除了喜欢玩石子以外，还喜欢吃果子。
乐乐现在有好多堆的果子，因为每堆果子的数量都不同，所以乐乐可以很放心地把这几堆果子的数量放在一个集合 S 里。现在，乐乐想从这个集合里面找出一个特殊的子集 S'，要求满足下面的性质：
- 满足集合的所有性质
- 对任意一个
S'内的元素x，不存在一个数y，使得y = kx并且y属于S'。即S'中的任意一个数，它乘以k之后的数都不在S'内
Input Format
第 1 行：两个整数： n 和 k
第 2 行：n 个整数： a[i] 表示给定的集合
Output Format
一个整数： 表示最大的满足要求的子集的大小
Sample Input
6 2
2 3 6 5 4 10
Sample Output
3
Limits
- 对于 30% 的数据：
n, k ≤ 100 - 对于 40% 的数据：
a[i] ≤ 2^31 - 1 - 对于 70% 的数据：
n, k ≤ 5000 - 对于 100% 的数据：
n, k ≤ 10^5,a[i] ≤ 2^63 - 1
Hint
在样例所给集合中，找出的最大的满足要求的子集为 {4, 5, 6}
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！