Part 1：前言

题目翻译

在他最喜欢的咖啡馆里，Kmes再次想尝尝皮草大衣下的鲱鱼。以前，这对他来说并不难，但咖啡馆最近推出了一项新的购买政策。

现在，为了进行购买，Kmes需要解决以下问题：在他面前摆放着 \(n\) 张不同价格的卡，第 \(i\) 张卡的价格为 \(a_i\)，在这些价格中没有整数 \(x\)。

Kmes被要求将这些卡划分为最少数量的坏段（这样每张卡只属于一个段）。如果无法选择乘积等于 \(x\) 的卡子集，则认为该段是坏的。Kmes 划分卡片的所有段都必须是坏的。

从形式上讲，如果没有下标 \(i_1<i_2<\ldots<i_k\)，使得 \(l\le i_1,i_k\le r\) 且 \(\prod _ {j=1} ^ {k} a_{i_j} = x\)，则段 \((l,r)\) 是坏的。

帮助Kmes确定坏段的最小数量，以便享受他最喜欢的菜肴。

输入格式

第一行包含一个整数 \(t（1\le t\le 10^3）\)——测试用例的数量。

每组输入数据的第一行分别给出整数 \(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\)。

输出格式

对于每组输入数据，输出坏段的最小数量。

Part 2：思路

这道题，咱就选择贪心吧（主要是我 dp 不大会）。

坏段 \(B\) 的定义：\(\exist\) 子序列 \(A \in B, \prod A=x\)。

显然，一个坏段的长度是有单调性的：当 \(a_1,a_2,\dots,a_k\) 是坏段时，\(a_1,a_2,\dots,a_{k+1}\) 也必定是坏段。

所以，我们每次判断出一个段是坏段时，就把 ans 加一。

怎么判断呢？考虑用一个速度更快的 unordered_set，存储之前所有子序列的乘积。

每次循环遍历这个 unordered_set，令当前遍历到的为 \(k\)。当 \(a_i \times k=x\) 时，我们就知道，已经有一个坏段产生了。我们把 unordered_set 清空，将 ans 加一。

但是这样时间复杂度太高，极端情况下，复杂度为 \(O(nx) \approx 10^{10}\)，即使 4s 时限，也救不了你。

所以我们要考虑优化。

• 当 \(x \bmod (a_i \times k)=0\) 时，将 \(a_i \times k\) 放入 unordered_set 里。

• 当 \(x \bmod(a_i \times k)\neq 0\) 时，由于无论之后的数怎么样，子序列的乘积已经 \(\neq x\) 了，就舍去。

Part 3：代码

你们终于来到了这里

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll t,n,x,a[N],ans;
unordered_set<ll> st,us;
inline void FIO(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #define endl '\n'
} 
inline void work(){
	st.clear();us.clear();ans=1;
	cin>>n>>x;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		for(auto j:st){
			ll k=a[i]*j;
			if(x%k==0){
				if(k==x){
					ans++;st.clear();us.clear();
					break;
				}
				us.insert(k);
			}
		}
		for(auto j:us) st.insert(j);
		us.clear();
		if(x%a[i]==0) st.insert(a[i]);
	}
	cout<<ans<<endl;
}
signed main(){
    FIO();
    cin>>t;
    while(t--) work();
}