275C - k-Multiple Free Set - CodeForces Solution

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

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const ll INF = 1e9;

int main() {
    ios_base::sync_with_stdio(0); 
    cin.tie(0);

    long long n, k;
    cin >> n >> k;

    vector<long long> arr(n);
    set<long long> num_set;
    for (int i =  0; i < n; i++) {
        cin >> arr[i];
        num_set.insert(arr[i]);
    }
    sort(arr.begin(), arr.end());
    set<long long> seen;
    int total_size = 0;
    for (int i = 0; i < n; i++) {
        if (seen.find(arr[i]) == seen.end()) {
            long long num = arr[i];
            int count = 1;
            seen.insert(num);
            while (num_set.find(num*k) != num_set.end() && seen.find(num*k) == seen.end()) {
                count += 1;
                num *= k;
                seen.insert(num);
            }
            if (count % 2 == 0) {
                total_size += count / 2;
            } else {
                total_size += (count + 1)/2;
            }
        }
    }
    cout << total_size;

    
}