← 返回题目列表

Codeforces · 274/A

A. k-多重自由套装

中文机器翻译题面 查看原题

k 重自由集是一组整数,其中不存在其中一个整数等于另一个整数乘以 k 的整数对。也就是说,集合中不存在两个整数 x 和 y (x < y),使得 y = x·k。

给你一组 n 个不同的正整数。你的任务是找到它的最大 k 重自由子集的大小。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 105, 1 ≤ k ≤ 109)。下一行包含 n 个不同正整数 a1, a2, ..., an (1 ≤ ai ≤ 109) 的列表。

行中的所有数字均以单个空格分隔。

输出

在输出的唯一一行上打印 {a1, a2, ..., an} 的最大 k 重自由子集的大小。

示例

输入 #1

6 2
2 3 6 5 4 10

输出 #1

3

注意

在样本输入中,可能的最大 2 重自由子集之一是 {4, 5, 6}。