P4411 [BJWC2010] Number Picking Game

Xiao C has just learned the Euclidean algorithm and is enjoying it, but Xiao P comes to make trouble and leaves Xiao C with a hard problem. You are given $N$ numbers, denoted by $a_1, a_2, \cdots, a_n$. Now Xiao P asks Xiao C to pick numbers one by one in order. The first number can be chosen arbitrarily. Suppose the current number is $a_j$. To pick the next number $a_k$ with $k > j$, the number $a_k$ must satisfy $\mathrm{gcd}(a_j, a_k) \ge L$. How many numbers should be picked? Naturally, as many as possible. Needless to say, this is not only a challenge for Xiao C, but also for you.

The first line contains two numbers $N$ and $L$. The second line contains $N$ numbers separated by spaces: $a_1, a_2, \cdots, a_n$.

Output a single line with one number, the maximum count of numbers that can be picked according to the rule.

### Sample Explanation Pick $3$ numbers: $16, 24, 6$. $\mathrm{gcd}(16, 24) = 8$, $\mathrm{gcd}(6, 24) = 6$. ### Constraints For 30% of the testdata, $N \le 1000$. For 100% of the testdata, $N \le 50\,000$, $2 \le L \le a_i \le 1\,000\,000$. Translated by ChatGPT 5