k倍多重正整数集合

/*
找规律
*/
#include <bits/stdc++.h>
using namespace std;

int main()
{
//  freopen("input.txt","r",stdin);
    int n, k, i, x, t_min;
    cin >> n >> k;
    map<int, int> dic;
    for(i = 0; i < n; i++) {
        cin >> x;
        dic[x]++;
    }
    if(k == 1) {
        cout << dic.size() << endl;
        return 0;
    }
    for(auto it = dic.begin(); it != dic.end(); it++) {
        if(dic.find(it->first * k) == dic.end()) continue;
        if(it->second < 1 || dic[it->first * k] < 1) continue;
        t_min = min(it->second, dic[it->first * k]);
        n -= t_min;
        it->second -= t_min;
        dic[it->first * k] -= t_min;
    }
    cout << n << endl;
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k,x,t;
    cin>>n>>k;
    map<int, int> M;
    for(int i=0;i<n;i++){
        cin>>x;
        M[x]++;
    }
    if(k==1){
        cout<<M.size()<<endl;
    }else{
        for(map<int,int>::iterator it=M.begin();it!=M.end();it++){
            x = (it->first)*k;
            if(M.find(x)==M.end())
                continue;
            if(it->second==0 || M[x]==0)
                continue;
            t = min(it->second, M[x]);
            n -= t;
            M[x] -= t;
            it->second -= t;
        }
        cout<<n<<endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <cstdio>
using namespace std;

int main(){
    int n,k,tmp;
    map<int,int> dict;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>tmp;
        dict[tmp]++;
    }
    int ans=0;
    if(k==1){
        ans = dict.size();
        cout<<ans<<endl;
        return 0;
    }
    for(map<int,int>::iterator it=dict.begin();it!=dict.end();it++){
        if(it->second==0) continue;
        vector<int> v;
        vector<decltype(it)> its;
        for(auto kit = it;kit!=dict.end();kit = dict.find(kit->first*k)){ // log_k(max(a))
            v.push_back(kit->second);
            its.push_back(kit);
            kit->second = 0;
            // printf("v: %d, count: %d\n",kit->first, kit->second);
        }
        if(v.size()==1){
            ans += v[0];
            continue;
        }
        if(v.size()==2){
            ans += max(v[0],v[1]);
            continue;
        }
        // 问题转化成了: 在数组v中, 找出子序列的最大和, 要求子序列满足选取的数组元素之间要么隔了1个数要么隔了2个数
        vector<int> f(v.size()); // 递推方程: f[i] = v[i] + max(f[i-2], f[i-3])
        f[0] = v[0];
        f[1] = v[1];
        f[2] = v[0]+v[2];
        for(int i=3;i<v.size();i++){
            f[i] = v[i] + max(f[i-2], f[i-3]);
        }
        ans += max(f[v.size()-1], f[v.size()-2]);
    }
    cout<<ans<<endl;
    return 0;
}

import java.util.*;
public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Long n = (long) sc.nextInt();
        Long k = (long) sc.nextInt();
        Map<Long, Integer> map = new TreeMap<>();
        for(int i = 0; i < n; i++){
            Long x = (long) 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;
        for(Long 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);
        
    }
}