题目

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
#define ll long longconst int maxn = 1e6 + 5, inf = 1e18, maxm = 4e4 + 5, base = 37;
const int N = 1e4;
// const int mod = 1e9 + 7;
// const int mod = 998244353;
const __int128 mod = 212370440130137957LL;int n, m;
int a[maxn], b[maxn];
//long long ? maxn ? n? m?void solve(){ll res = 0;int x;cin >> n >> x;for(int i = 1; i <= n; i++){cin >> a[i];}vector<int> divs;divs.pb(0);vector<int> id(x + 1, 0);for(int i = 1; i * i <= x; i++){if(x % i == 0){divs.pb(i);// id[i] = divs.size() - 1;if(x / i != i){divs.pb(x / i);// id[x / i] = divs.size() - 1;}}}int sz = divs.size() - 1;sort(divs.begin() + 1, divs.begin() + sz + 1);//排序因为后面要从大的因数开始更新for(int i = 1; i <= sz; i++){id[divs[i]] = i;//x的因数到编号的映射}vector<int> can(sz + 1, 0);//can[i]表示因数divs[i]能不能被凑出can[1] = 1;res = 1;for(int i = 1; i <= n; i++){if(x % a[i] != 0) continue;//不是x的因数，直接忽略if(can[id[x / a[i]]]){res++;can.assign(sz + 1, 0);can[1] = 1;can[id[a[i]]] = 1;continue;}//必须从大的因数开始更新can，//设//下标 : 1 2 3 4//divs : 1 2 4 8//can  : 1 0 0 0//当前数a[i] : 2//若从小的因数开始更新，那么更新之后//can  : 1 1 1 1 （显然错误）for(int j = sz; j >= 1; j--){if(divs[j] % a[i] == 0 && can[id[divs[j] / a[i]]]){can[j] = 1;}}}cout << res << '\n';
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout << fixed << setprecision(9);int T = 1;cin >> T;while (T--){solve();}return 0;
}