274A - k-Multiple Free Set - CodeForces Solution

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int MAX = 100005;
 
int n, k, x, y, p;
int a[MAX], b[MAX];
 
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> k;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
 
    if(k == 1){
        cout << n << endl;
        return 0;
    }
 
    for(int i = 0; i < n; i++){
        y = a[i];
        b[i] = 1;
        if(y % k != 0) continue;
        x = y / k;
        p = lower_bound(a, a + n, x) - a;
        if(a[p] == x){
            b[i] = b[p] + 1;
            b[p] = 0;
        }
    }
 
    int ans = 0;
    for(int i = 0; i < n; i++){
        ans += (b[i] + 1) / 2;
    }
 
    cout << ans << endl;
 
    return 0;
}