Skip to content

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 行:两个整数: nk

第 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了,可以的话,请您参考添加页面,与大家一起分享你的题解!