二、数学推导核心
等式等价条件所有 pi两两互质。 原理：若两个数共享质因子，lcm 只会保留一次该质因子，乘积会保留两次，等式不成立。
单个质数分配规则对任意质数 pr，最多只能出现在一个 pi 中。 定义 (v_pr(x))：x 分解质因数后 pr 的指数。 对数字 ai，pi 中 pr 指数可取 v_pr(ai))。
该质数全部分配方案分两类：
- 所有人都不用这个质数：1 种；
- 选某个人使用，给它分配 v_pr(ai)) 的指数
三、解题思路
- 预处理线性筛，求出10^6 每个数的最小质因子 ，快速分解任意数字质因数；
- 每组测试用例：
- 遍历所有 ai，逐个分解质因数；
- 用哈希表统计每个质数在全部数字里的总指数；
- 去重拿到所有出现过的质数；
- 遍历所有质数，把每个质数的 sum+1 累乘，模 10^9+7，得到答案。
四、完整代码
#include <bits/stdc++.h> using namespace std; #define int long long const int MOD = 1e9 + 7; const int MAX = 1e6 + 5; int lp[MAX]; int a[MAX]; vector<int> primes; int read() { int x; cin >> x; return x; } // 计算单组答案 int calc(int n) { map<int, int> sum_exp; set<int> used_pr; for (int i = 1; i <= n; i++) { int num = a[i]; int cur = num; while (cur > 1) { int p = lp[cur]; used_pr.insert(p); sum_exp[p]++; cur /= p; } } int ans = 1; for (int p : used_pr) { ans = ans * (sum_exp[p] + 1) % MOD; } return ans; } int32_t main() { // 线性筛预处理最小质因子 lp[1] = 1; for (int i = 2; i < MAX; i++) { if (!lp[i]) { lp[i] = i; primes.push_back(i); } for (int p : primes) { if (p > lp[i] || i * p >= MAX) break; lp[i * p] = p; } } int t = read(); while (t--) { int n = read(), x = read(); // x固定1，无作用 for (int i = 1; i <= n; i++) a[i] = read(); cout << calc(n) << '\n'; } return 0; }五、代码模块说明
线性筛预处理全局只运行一次，得到每个数的最小质因子，分解质因数 (O(log x))。
calc 核心函数
sum_exp[p]：质数 p 在所有 (ai) 中的总指数；used_pr：去重，存储所有出现过的质数；- 按公式累乘每个质数的方案数，取模。
- 输入处理每组读入 (n,x)（x 废弃），读入数组，调用计算函数输出。
六、复杂度分析
- 筛预处理：(O(10^6))，一次性开销；
- 每组分解所有数字质因数：总复杂度 (O(sum n log ai))； (sum n le 10^5)，数据范围完全通过。
七、易错点记录
- 乘法会溢出，必须统一
long long，每次相乘取模； - 同一个质数只乘一次，必须用 set 去重；
- 指数是分解时每出现一次质因子都 + 1，不是统计数字出现次数；
- 简单版 (x=1)，输入的 x 不需要参与任何计算；
- 模数 (10^9+7) 不要写错。
