Description

A set is a concept in mathematics. In plain words, a set is a bunch of numbers grouped together.

A set has the following properties:

• Unorderedness: within any set, every element has the same status, and the elements are unordered.
• Distinctness: in a set, any two elements are considered different; that is, each element can appear at most once.
• Definiteness: for a given set and any given element, the element either belongs to the set or does not; there is no ambiguity.

For example, $A = \{ 1, 2, 3 \}$ is a set. We can see that $1$ belongs to $A$, i.e., $1 \in A$; $4$ does not belong to $A$, i.e., $4 \notin A$. The size of a set is the number of its elements.

Now we define a special $k$-set, which must satisfy:

• All the properties of sets.
• For any element $x$ in the set, there does not exist a number $y$ such that $y = k x$ and $y$ also belongs to the set. In other words, for any number in the set, the number obtained by multiplying it by $k$ is not in the set.

You are given a set consisting of $n$ distinct integers. Please find a largest $k$-set contained in this set.

Input Format

The first line: two integers, $n$ and $k$.

The second line: $n$ integers, $a_i$ are the elements of the given set.

Output Format

The first line: one integer, $\mathit{ans}$, the size of a largest $k$-set.

6 2	
2 3 6 5 4 10

3

Hint

Hint: In the set given in the sample, a largest $2$-set is $\{ 4, 5, 6 \}$.

• For $30 \%$ of the testdata: $n, k \le 100$.
• For $40 \%$ of the testdata: $a_i \le 2^{31} - 1$.
• For $70 \%$ of the testdata: $n, k \le 5000$.
• For $100 \%$ of the testdata: $2 \le n, k \le {10}^5$, $1 \le a_i \le 2^{63} - 1$.

Translated by ChatGPT 5