解法

好久没写代码了，傻乎乎的写了个并查集摆在这。。。
正解代码很短

代码

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define deubg_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7; 

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

void pt() { cerr << endl; }
template<typename Head, typename... Tail> void pt(Head H, Tail... T) { cerr << ' ' << H; pt(T...); }


//--------------------------------------------
int N,K;
int fa[maxn],sz[maxn];
ll a[maxn];
map<ll,int> mp;
int zero = 0;
int find(int x){
    return x == fa[x] ? x :fa[x] = find(fa[x]);
}

void solve(){
    sort(a+1,a+N+1);
    for(int i = 1;i<=N;i++) fa[i] = i,sz[i] = 1;
    for(int i = 1;i<=N;i++){
        if(a[i] == 0) continue;
        if(a[i]%K == 0 && mp.count( a[i]/K )){
            int fx = find(i), fy = find(mp[ a[i]/K ]);
            fa[fx] = fy;
            sz[fy] += sz[fx];
        }
        mp[a[i]] = i;
    }    
    int ans = 0;
    for(int i = 1;i<=N;i++){
        if(find(i) == i){
            ans += (sz[i] + 1)/2;
        }
    }
    printf("%d\n",ans);
}
int main(){
//    debug_in;

    read(N,K);
    for(int i = 1;i<=N;i++) {
        read(a[i]);
        if(a[i] == 0) zero++;
    }
    if(K) solve();
    else {
        cout<<N - zero<<'\n';
    }

    return 0;
}