P1978 Set

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.

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

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

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