k倍多重正整数集合

题解：
题目难度：三星

考察点： 哈希，思维

易错点：

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

题解：

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

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

#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;
}