k倍多重正整数集合

题解：
题目难度：三星

考察点： 哈希，思维

易错点：

很多同学在枚举倍数的时候会漏掉当 $k$ 的值为 $1$ 的情况，事实上，这种情况需要单独讨论， $k$ 的值为1时，集合最大可容纳的元素个数就是集合中元素的种数，也就是让集合中不同的元素只能出现1次。

题解：

这题的数据范围为 $10^5$ ，因此如果对于每个位置暴力去探寻它的 $k$ 倍是否存在与序列种显然是不可行的，因为这样复杂度为 $O(n^2)$ ， $1s$ 的时间内承受不住这么高的复杂度。可以通过空间换时间的方法来进行处理，通过哈希表来处理，这里建议选用 $map$ ， $map$ 的底层是颗红黑树，当作哈希表使用查询的复杂度是 $O(log_2n)$ 的，同时 $map$ 是有序的，可以保证枚举的时候是从小到大进行枚举的。

对于 $k$ 为 $1$ 的情况，可以直接参照易错点中所述，输出元素的类数即可。对于 $k$ 不为 $1$ 的情况，用 $map$ 统计出每个数出现的次数，然后对 $map$ 中的数从小到大进行枚举，如果当前数的 $k$ 倍在序列中，且当前数的个数不为0(因为是从小到大枚举的，很可能当前数被更小的数删除过)。则在序列中二者不能同时存在，选取二者中的出现次数更小的，将其从序列中删除，最后删完所有数，序列中余下的就是所求，复杂度 $O(nlog_2n)$

#include "bits/stdc++.h"
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
map<LL,int>mp;
int n;
LL k,a[maxn];
int main()
{
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        mp[a[i]]++;
    }
    if(k==1){
        printf("%d\n",mp.size());
    }else{
        for(auto &x:mp){
            if(mp.find(x.first*k)==mp.end()) continue;
            int mi=min(x.second,mp[x.first*k]);
            n-=mi;
            x.second-=mi;
            mp[x.first*k]-=mi;
        }
        printf("%d\n",n);
    }
    return 0;
}