CF1992F Valuable Cards

在他最喜欢的咖啡馆，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$），表示测试用例的数量。 每组测试数据的第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 10^5, 2 \le x \le 10^5$），分别表示卡片数量和整数 $x$。 每组测试数据的第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 2 \times 10^5, a_i \neq x$），表示卡片上的价格。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试数据，输出一个整数，表示最少需要划分的坏区间数量。

由 ChatGPT 4.1 翻译