k倍多重正整数集合

k倍多重正整数集合的定义是：在一个多重集合（元素可以重复）中，不存在一个正整数是另一个正整数的k倍。

现在小M有n个正整数，你可以选择其中一些数构成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
输出例子1:
3
例子1说明:
第一个样例中，我们选择2，3，5即可满足要求，因为k == 2，不存在一个数是另一个数的两倍。

输入例子2:
2 2
2 2
输出例子2:
2
例子2说明:
第二个样例中，我们选择2，2即可满足要求，因为k == 2，2也不是2的两倍，注意多重集合元素可以重复。

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Map<Integer, Integer> map = new TreeMap<>();//key有序的Map
        for(int i = 0; i < n; i++){
            int x = sc.nextInt();
            if(!map.containsKey(x)){
                map.put(x, 1);
            }else{
                map.put(x, map.get(x)+1);
           }
        }
        if(k == 1){
            System.out.println(map.size());
            return;
        }
        int count = 0;
        //在key是有序的情况下，从前往后遍历进行消除就OK，这样尽量保留两边的数，不保留中间的数
        //使用中间数，会使得1/k和k倍数都不可用，从而不满足尽可能多的要求
        for(Integer key : map.keySet()){ //抵消掉成倍数关系的数
            while(map.get(key)>=1 && map.containsKey(key*k) && map.get(key*k) >= 1){
                count++;
                map.put(key, map.get(key)-1);
                map.put(key*k, map.get(key*k)-1);
            }
        }
        System.out.println(n-count);
        
    }
}