A8952 | $k-Multiple Free Set$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

A $k$ -multiple free set is a set of integers where there is no pair of integers where one is equal to another integer multiplied by $k$ . That is, there are no two integers $x$ and $y$ $(x<y)$ from the set, such that $y=x\cdotk$ . You're given a set of $n$ distinct positive integers. Your task is to find the size of it's largest $k$ -multiple free subset.

The first line of the input contains two integers $n$ and $k$ ( $1<=n<=10^{5},1<=k<=10^{9}$ ). The next line contains a list of $n$ distinct positive integers $a_{1},a_{2},...,a_{n}$ $(1<=a_{i}<=10^{9})$ . All the numbers in the lines are separated by single spaces.

On the only line of the output print the size of the largest $k$ -multiple free subset of ${a_{1},a_{2},...,a_{n}}$ .

输入 #1

6 2
2 3 6 5 4 10

输出 #1

C++ 编辑器

输入

输出