Codeforces Round 957 (Div. 3) |
---|
Закончено |
В своём любимом кафе Kmes захотел в очередной раз отведать селёдку под шубой. Раньше ему бы не доставило труда сделать это, однако кафе недавно выдвинуло новую политику покупки.
Теперь для её совершения Kmes надо решить следующую задачу: перед ним на стол выкладывают $$$n$$$ карточек с ценами на разные позиции, на $$$i$$$-й карточке написано число $$$a_i$$$, среди этих цен нет целого положительного числа $$$x$$$.
Kmes просят разбить эти карточки на минимальное количество плохих отрезков (так, чтобы каждая карточка принадлежала ровно одному отрезку). Плохим считается такой отрезок, что в нём нельзя выбрать подмножество карточек с произведением, равным $$$x$$$. Все отрезки, на которые Kmes разобьёт карточки, должны быть плохими.
Формально, отрезок $$$(l, r)$$$ плохой, если не существует индексов $$$i_1 < i_2 < \ldots < i_k$$$, что $$$l \le i_1, i_k \le r$$$, и $$$a_{i_1} \cdot a_{i_2} \ldots \cdot a_{i_k} = x$$$. Помогите Kmes определить минимальное количество плохих отрезков, чтобы насладиться любимым блюдом.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов тестовых данных.
В первой строке каждого набора входных данных вам даны $$$2$$$ числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 10^5, 2 \le x \le 10^5$$$) — количество карточек и число соответственно.
Во второй строке каждого набора входных данных содержится $$$n$$$ чисел $$$a_i$$$ ($$$1 \le a_i \le 2 \cdot 10^5, a_i \neq x$$$) — цены на карточках.
Гарантируется, что сумма $$$n$$$ по всем наборам тестовых данных не превышает $$$10^5$$$.
Для каждого набора входных данных выведите минимальное количество плохих отрезков.
86 42 3 6 2 1 29 10000050000 25000 12500 6250 3125 2 4 8 165 21 1 1 1 18 64 3 4 3 4 3 4 37 126 11 1 3 11 10 210 52 4 4 2 4 4 4 3 1 17 84 6 5 1 2 4 18 273 9 17 26 2 20 9 3
3 2 1 1 2 1 3 3
Название |
---|