题意简述

给定数组 $a$ 和整数 $x$（$x$ 不在数组中）。将数组划分成最少个连续段，使得每一段内不存在一个子序列其乘积等于 $x$。求最少段数。

关键观察

• 只有 $x$ 的因数才可能参与构成 $x$。非因数可以直接忽略。
• 子序列可以不连续地跳过元素，因此段内只要存在一组因数的乘积等于 $x$，该段就是“好的”。为了保持段“坏”，必须切断乘积的形成路径。
• 从左到右维护当前段内所有可能形成的、$< x$ 的因数乘积集合（使用 can 数组标记哪些因数可达）。当遇到一个因数 $d$ 时，检查是否已存在某个可达乘积 $v$ 使得 $v \cdot d = x$。若存在，则当前段必须在此前结束，之后以 $d$ 开启新段。

算法步骤

1. 预处理 $x$ 的所有因数，建立数值到索引的映射 $idx$。
2. 布尔数组 $can$ 大小为因数个数，$can[idx[1]] = true$，ans = 1。
3. 遍历 $a$：
   • 若 $a_i$ 不是 $x$ 的因数，或 $a_i = 1$（$1$ 不改变乘积集合），跳过。
   • 令 $d = a_i$。若 $can[idx[x/d]]$ 为真，说明再加入 $d$ 立刻得到 $x$，必须切段：
     • ans++；
     • 重置 can 为全 false，再设 $can[idx[1]] = true$；
     • 将 $d$ 加入新段$（can[idx[d]] = true）$。
   • 否则，将 $d$ 正常加入：枚举所有当前可达因数 $f$，计算 $p = f \cdot d$。
     • 关键：只有当 $p < x$ 且 $x \bmod p = 0$（即 $p$ 仍是 $x$ 的因数）时，才将 idx[p] 标记为可达。因为非因数不可能最终乘出 $x$，忽略它们不会影响后续判断。
4. 输出 ans。

时间复杂度：$x$ 的因数个数 $\le 128$，每个元素最多枚举全部因数，总复杂度 $O(\sum n \cdot \sigma_0(x))$，足以通过。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 200000;

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    // 获取 x 的所有因数
    vector<int> factors;
    for (int i = 1; i * i <= x; ++i) {
        if (x % i == 0) {
            factors.push_back(i);
            if (i * i != x) factors.push_back(x / i);
        }
    }
    sort(factors.begin(), factors.end());
    int sz = factors.size();

    // 建立因数到索引的映射
    vector<int> idx(MAXV + 1, -1);
    for (int i = 0; i < sz; ++i) idx[factors[i]] = i;

    vector<bool> can(sz, false);
    can[idx[1]] = true;
    int ans = 1;

    for (int num : a) {
        if (num > x || x % num != 0) continue; // 非因数跳过
        if (num == 1) continue;                // 1 不影响

        int d = num;
        int need = x / d;
        int need_idx = idx[need];               // need 一定在因数中

        if (can[need_idx]) {
            // 会形成 x，必须切段
            ++ans;
            fill(can.begin(), can.end(), false);
            can[idx[1]] = true;
            // 将 d 加入新段（只有 1 和 d 可达）
            can[idx[d]] = true;
        } else {
            // 正常扩展可达集合
            vector<int> new_factors;
            for (int i = 0; i < sz; ++i) {
                if (can[i]) {
                    long long prod = 1LL * factors[i] * d;
                    if (prod < x && x % prod == 0) { // 必须仍是因数
                        new_factors.push_back(idx[prod]);
                    }
                }
            }
            for (int id : new_factors) can[id] = true;
        }
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}