题解 | k倍多重正整数集合

import sys

n, k = map(int, input().split())
ls = list(map(int, input().split()))
dict1 = {}
for i in ls:
    dict1[i] = dict1.get(i,0) + 1
# print(dict1)

# 如果k为1，直接输出不同的数的数量
if k == 1:
    print(len(dict1))
else:
    # 初始化抵消计数
    count = 0

    # 遍历Counter的键
    for key in sorted(dict1):
        while dict1[key] >= 1 and key * k in dict1 and dict1[key * k] >= 1:
            count += 1
            dict1[key] -= 1
            dict1[key * k] -= 1

    print(n-count)