阅读量:0
#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 long const 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; }