满分解法（100 分）

把因数个数写成质因数指数的乘积

困难在于，$b_i$ 的取值很多，而每个位置对同一个乘数的收益又不相同。先看乘上一个质数会改变什么。

若 $x=\prod_p p^{e_p}$，它的每个正因数都由各质数的指数独立选出，第 $p$ 项有 $e_p+1$ 种选择，因此

$$\tau(x)=\prod_p(e_p+1).$$

给 $x$ 再乘一个质数 $p$，只会把对应的因子从 $e_p+1$ 改成 $e_p+2$，其他质数的贡献完全不变。

先确定可以把 $k$ 全部用完。若某个可行方案中 $B=\prod_i b_i<k$，因为 $B\mid k$，剩余的 $k/B$ 中至少有一个质因数。把它乘到任意一个 $b_i$ 上，方案仍然合法，而且对应的因数个数严格增加。因此最优方案一定满足 $B=k$；$k=1$ 时则只能全部取 $b_i=1$。

不同质数可以分别决定分配

设

$$k=\prod_{p\mid k}p^{E_p}.$$

对固定的质数 $p\mid k$，记 $e_i$ 为原来 $a_i$ 中 $p$ 的指数，$t_i$ 为分配给 $b_i$ 的 $p$ 的个数。合法分配恰好满足

$$t_i\ge0,\qquad\sum_{i=1}^n t_i=E_p,$$

而这个质数对目标的贡献是

$$\prod_{i=1}^n(e_i+t_i+1).$$

不同质数的额度约束互不影响，目标也只是把它们的贡献相乘。把各个质数的最优分配合在一起，令 $b_i=\prod_{p\mid k}p^{t_i}$，就会得到乘积恰为 $k$ 的合法序列。因此可以分别最大化各个质数的贡献，再相乘。

不整除 $k$ 的质数不能分配，其贡献保持不变。实现时，每处理一个 $p\mid k$，就从所有 $a_i$ 中除尽 $p$，并记录除去的次数。所有这类质数都处理完以后，剩余值记为 $r_i$，它只含不能改变的质因数，最后再乘上 $\prod_i\tau(r_i)$ 即可。

一份质因子应该给谁

现在只考虑一种质数。假设某个位置当前的指数为 $e$，给它增加一份质因子的倍率为

$$\frac{e+2}{e+1}=1+\frac1{e+1}.$$

$e$ 越小，这个倍率越大。于是每次选取当前指数最小的位置，给它加一，再进行下一次选择。比较的是这个质数的指数，不是 $a_i$ 的大小，也不是 $\tau(a_i)$。

例如当前指数为 $(0,1,3)$，要分配三份同一种质因子：

已分配份数	一种贪心分配后的指数	当前贡献
$0$	$(0,1,3)$	$1\times2\times4=8$
$1$	$(1,1,3)$	$2\times2\times4=16$
$2$	$(2,1,3)$	$3\times2\times4=24$
$3$	$(2,2,3)$	$3\times3\times4=36$

第一次加一后，需要重新比较。若把三份都给原先最小的位置，得到 $(3,1,3)$，贡献只有 $32$。

只比较当前倍率还需要说明不会影响后面的最优性。设位置 $u$ 的当前指数最小。取一个最优的剩余分配：若它已经给 $u$ 至少一份，就可以先给这一份；否则，选择一个得到至少一份的位置 $v$，从它转移一份给 $u$。

设 $v$ 在这个方案中的最终指数为 $y$。由于它至少得到一份，且原来的指数不小于 $e_u$，有 $y\ge e_u+1$。转移前后，这两个位置的贡献之差为

$$(e_u+2)y-(e_u+1)(y+1)=y-e_u-1\ge0.$$

所以总能找到一个同样最优的方案，让当前最小的位置先得到一份。完成这一步后，问题仍是同样的分配问题，对剩余份数重复论证即可。相同指数任选一个位置都成立。

用有限次扫描完成分配

$k$ 中所有质因子的总份数记为 $S=\sum_p E_p$。每一份至少是 $2$，所以 $2^S\le k$。本题 $k\le3\times10^5$，从而 $S\le18$。

因此每次直接扫描 $n$ 个指数，找到最小值即可；全部质数合计至多扫描 $18$ 次。每个质数分配完毕后，把所有最终的“指数加一”乘入答案。

为了计算剩余值的因数个数，令 $A=\max_i a_i$ 为原输入的最大值，预处理 $1$ 到 $A$ 的因数个数。枚举一个因数 $d$，给它的所有倍数 $d,2d,3d,\ldots$ 各加一。每对整除关系恰好统计一次，因此表中保存的就是 $\tau(x)$，其中 $\tau(1)=1$。

完整步骤是：先预处理因数个数并分解 $k$；随后逐个处理 $k$ 的质因数，提取各位置的指数、逐份执行贪心、累乘对应贡献；最后累乘剩余值的因数个数。全程只保存指数和逐步取模的乘积，无需构造 $a_i b_i$。取模仅用于记录已经确定的最优乘积，不参与方案优劣的比较。

时间复杂度为 $O(A\log(A+1)+n\log(A+1)+n\log(k+1)+\sqrt{k})$。因数表共更新 $\sum_{d=1}^A\lfloor A/d\rfloor$ 次；提取指数时，每次成功除法都使某个值至少减半；逐份寻找最小值共 $nS$ 次比较；$k$ 用试除分解。

空间复杂度为 $O(A+n+\log(k+1))$，包括因数表、剩余值、当前质数的指数和 $k$ 的分解结果。

AC 代码（C++20）

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

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int& x : a) cin >> x;
  const int limit = *max_element(a.begin(), a.end());
  constexpr int mod = 998244353;
  vector<int> div_cnt(limit + 1);
  for (int d = 1; d <= limit; d++) {
    for (int j = d; j <= limit; j += d) div_cnt[j]++;
  }
  vector<pair<int, int>> factors;
  int x = k;
  for (int p = 2; p <= x / p; p++) {
    if (x % p != 0) continue;
    int cnt = 0;
    while (x % p == 0) {
      x /= p;
      cnt++;
    }
    factors.push_back({p, cnt});
  }
  if (x > 1) factors.push_back({x, 1});
  i64 ans = 1;
  for (auto [p, cnt] : factors) {
    vector<int> exponent(n);
    for (int i = 0; i < n; i++) {
      while (a[i] % p == 0) {
        a[i] /= p;
        exponent[i]++;
      }
    }
    while (cnt--) {
      auto it = min_element(exponent.begin(), exponent.end());
      (*it)++;
    }
    for (int e : exponent) ans = ans * (e + 1) % mod;
  }
  for (int x : a) ans = ans * div_cnt[x] % mod;
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

逐个枚举因数（通过子任务 2、4，共 50 分）

把因数统计留作直接枚举

当所有数都不超过 $10^4$ 时，可以保留朴素的因数个数计算：对一个数 $x$，枚举 $d=1,2,\ldots,x$，累计满足 $d\mid x$ 的个数。若 $n\le5$，即使 $a_i$ 达到 $3\times10^5$，这样统计也很快。

分配部分仍按质数处理。由 $\tau(\prod_p p^{e_p})=\prod_p(e_p+1)$，$k$ 中不同质因子的分配限制互相独立，目标是各自贡献的乘积；把所有剩余因子用完一定更优。固定 $p$，若各位置当前指数为 $e_i$，增加一次的倍率为 $(e_i+2)/(e_i+1)$，应优先增加当前最小指数。

这个选择可以用交换证明：若最优剩余方案没给最小指数 $x$ 分配，就从一个得到分配的位置移一份过来。设后者在方案中的最终指数为 $y$，则 $y\ge x+1$，两处乘积的变化是

$$(x+2)y-(x+1)(y+1)=y-x-1\ge0.$$

因此总有最优方案包含这次选择，之后可以继续选最小指数。比如 $a=(1,1,1,1,1,1),k=64$ 时，把六份 $2$ 分别给六个位置，得到 $2^6=64$；每次都重新找最小指数就会做出这样的分配。

先分解 $k$。对每个质数，反复除尽所有 $a_i$ 中的该因子，记录指数，逐份扫描并增加当前最小指数，最后乘入这一质数的全部贡献。所有质数处理完后，对剩余的每个 $a_i$ 逐个枚举正因数，乘入相应个数。余数不含可分配的质因数，故这一步恰好补足固定贡献。各次乘法及时对 $998244353$ 取模；分配规则不比较模值。

令 $A=\max_i a_i$。时间复杂度为 $O(nA+n\log(A+1)+n\log(k+1)+\sqrt{k})$，其中因数枚举的实际次数是各个剩余值之和，至多 $nA$。空间复杂度为 $O(n+\log(k+1))$。

子任务 $2$ 的因数枚举次数至多 $1.5\times10^6$，子任务 $4$ 至多 $10^8$，所以本方法覆盖子任务 $2,4$。全范围下 $nA$ 可达 $9\times10^{10}$，需要把重复的因数统计改为预处理。

参考代码（C++20）

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

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int& x : a) cin >> x;
  constexpr int mod = 998244353;
  vector<pair<int, int>> factors;
  int x = k;
  for (int p = 2; p <= x / p; p++) {
    if (x % p != 0) continue;
    int cnt = 0;
    while (x % p == 0) {
      x /= p;
      cnt++;
    }
    factors.push_back({p, cnt});
  }
  if (x > 1) factors.push_back({x, 1});
  i64 ans = 1;
  for (auto [p, cnt] : factors) {
    vector<int> exponent(n);
    for (int i = 0; i < n; i++) {
      while (a[i] % p == 0) {
        a[i] /= p;
        exponent[i]++;
      }
    }
    while (cnt--) {
      auto it = min_element(exponent.begin(), exponent.end());
      (*it)++;
    }
    for (int e : exponent) ans = ans * (e + 1) % mod;
  }
  for (int x : a) {
    int cnt = 0;
    for (int d = 1; d <= x; d++) {
      if (x % d == 0) cnt++;
    }
    ans = ans * cnt % mod;
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

枚举指数分配（通过子任务 1–2，共 25 分）

用小 $n$ 枚举每种质数的分配

增加任意一个剩余质因子都会让某个位置的因数个数变大，所以最优方案会用完 $k$。若 $x=\prod_p p^{e_p}$，由每个因数对各个指数的独立选择可得 $\tau(x)=\prod_p(e_p+1)$。

固定一个整除 $k$ 的质数 $p$。设它在 $k$ 中出现 $E$ 次，在各个 $a_i$ 中出现 $e_i$ 次。分配 $t_i$ 份给位置 $i$ 后，它对答案的贡献为

$$\prod_{i=1}^n(e_i+t_i+1),\qquad t_i\ge0,\quad\sum_i t_i=E.$$

不同质数的约束和贡献相互独立；各自的分配能通过 $b_i=\prod_p p^{t_i}$ 合成合法答案。因此可以独立求每个质数的最大贡献。

当 $n\le5$ 时，直接枚举所有 $t_i$。递归记录下一个位置、未分配份数和已确定位置的实际乘积。到一个位置时，枚举给它 $0$ 到全部剩余份数，乘上相应的 $e_i+t_i+1$；最后一个位置必须得到所有剩余份数。这样每个合法分配恰好出现一次，取叶子处乘积的最大值即可。比较期间不取模，最大值确定以后再乘入模意义下的答案。

例如两个位置的初始指数为 $(0,2)$，$E=2$。三种分配 $(t_1,t_2)=(0,2),(1,1),(2,0)$ 的贡献分别为 $5,8,9$，枚举就能选择最后一种，无需事先得出分配规则。

处理 $p$ 时从 $a_i$ 中除尽 $p$ 来获得 $e_i$。全部处理完后，剩余值只含不整除 $k$ 的质因数，其贡献不能改变，直接把它们的因数个数相乘。因数个数用枚举约数、更新其所有倍数的筛法预处理。

本方法对 $n\le5$ 成立。各个原始指数与 $E$ 都不超过 $18$，这里需要比较的单质数贡献至多为 $37^5$，可以直接保存实际整数。若 $k=1$，没有分配过程，任意 $n$ 都只执行因数个数相乘，所以也覆盖子任务 $1$。本方法声明覆盖子任务 $1,2$，对其他范围不保证递归成本与实际乘积的表示。

令 $A=\max_i a_i$。时间复杂度为 $O(A\log(A+1)+\sqrt{k}+n\log(A+1)+n\sum_{p\mid k}\binom{E_p+n-1}{n-1})$。每个质数有 $\binom{E_p+n-1}{n-1}$ 种非负分配，一条递归路径长度至多 $n$；当 $n\le5$ 时，每种质数至多 $\binom{22}{4}=7315$ 种分配。

空间复杂度为 $O(A+n+\log(k+1))$，包含输入、因数表、指数、分解结果与递归栈。

参考代码（C++20）

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

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int& x : a) cin >> x;
  const int limit = *max_element(a.begin(), a.end());
  constexpr int mod = 998244353;
  vector<int> div_cnt(limit + 1);
  for (int d = 1; d <= limit; d++) {
    for (int j = d; j <= limit; j += d) div_cnt[j]++;
  }
  vector<pair<int, int>> factors;
  int x = k;
  for (int p = 2; p <= x / p; p++) {
    if (x % p != 0) continue;
    int cnt = 0;
    while (x % p == 0) {
      x /= p;
      cnt++;
    }
    factors.push_back({p, cnt});
  }
  if (x > 1) factors.push_back({x, 1});
  i64 ans = 1;
  for (auto [p, cnt] : factors) {
    vector<int> exponent(n);
    for (int i = 0; i < n; i++) {
      while (a[i] % p == 0) {
        a[i] /= p;
        exponent[i]++;
      }
    }
    i64 best = 0;
    auto dfs = [&](auto&& self, int pos, int rem, i64 prod) -> void {
      if (pos == n - 1) {
        best = max(best, prod * (exponent[pos] + rem + 1));
        return;
      }
      for (int t = 0; t <= rem; t++) {
        self(self, pos + 1, rem - t, prod * (exponent[pos] + t + 1));
      }
    };
    dfs(dfs, 0, cnt, 1);
    ans = ans * (best % mod) % mod;
  }
  for (int x : a) ans = ans * div_cnt[x] % mod;
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}

至多一份质因子（通过子任务 1、3，共 20 分）

$k=1$ 与 $k=2$

当 $k=1$ 时，所有 $b_i$ 只能为 $1$，答案就是 $\prod_i\tau(a_i)$。

当 $k=2$ 时，可以使一个位置乘上 $2$，其余位置保持不变。使用这个因子会增加因数个数，因此一定会使用。

把 $a_i$ 写成 $2^{e_i}u_i$，其中 $u_i$ 为奇数，则 $\tau(a_i)=(e_i+1)\tau(u_i)$。若把唯一的 $2$ 分给位置 $i$，目标会乘上

$$\frac{e_i+2}{e_i+1}=1+\frac1{e_i+1}.$$

于是只需选择 $e_i$ 最小的位置，把它的指数加一。比如 $a=(9,8)$ 时，两个指数为 $0,3$，应让 $9$ 乘上 $2$：此时因数个数乘积为 $\tau(18)\tau(8)=24$，大于让 $8$ 乘上 $2$ 得到的 $15$。

用反复除以 $2$ 得到全部 $e_i,u_i$，根据 $k$ 决定是否增加一次最小指数，再计算 $\prod_i(e_i+1)\tau(u_i)$。预处理 $\tau$ 时，枚举每个正整数 $d$，给它的每个倍数的计数加一。每个真正的因数恰好贡献一次，故该表准确统计因数个数。

本方法保证 $k\in\{1,2\}$，覆盖子任务 $1,3$。代码中的一次分配只处理 $k=2$ 的情况，其他 $k$ 不属于适用范围。

令 $A=\max_i a_i$。时间复杂度为 $O(A\log(A+1)+n\log(A+1))$，空间复杂度为 $O(A+n)$。

参考代码（C++20）

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

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int& x : a) cin >> x;
  const int limit = *max_element(a.begin(), a.end());
  constexpr int mod = 998244353;
  vector<int> div_cnt(limit + 1);
  for (int d = 1; d <= limit; d++) {
    for (int j = d; j <= limit; j += d) div_cnt[j]++;
  }
  vector<int> exponent(n);
  for (int i = 0; i < n; i++) {
    while (a[i] % 2 == 0) {
      a[i] /= 2;
      exponent[i]++;
    }
  }
  if (k == 2) {
    auto it = min_element(exponent.begin(), exponent.end());
    (*it)++;
  }
  i64 ans = 1;
  for (int i = 0; i < n; i++) {
    ans = ans * (exponent[i] + 1) % mod * div_cnt[a[i]] % mod;
  }
  cout << ans << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
}