二、数学推导核心等式等价条件所有 pi两两互质。 原理若两个数共享质因子lcm 只会保留一次该质因子乘积会保留两次等式不成立。单个质数分配规则对任意质数 pr最多只能出现在一个 pi 中。 定义 (v_pr(x))x 分解质因数后 pr 的指数。 对数字 aipi 中 pr 指数可取 v_pr(ai))。该质数全部分配方案分两类所有人都不用这个质数1 种选某个人使用给它分配 v_pr(ai)) 的指数三、解题思路预处理线性筛求出10^6 每个数的最小质因子 快速分解任意数字质因数每组测试用例遍历所有 ai逐个分解质因数用哈希表统计每个质数在全部数字里的总指数去重拿到所有出现过的质数遍历所有质数把每个质数的 sum1 累乘模 10^97得到答案。四、完整代码#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]; vectorint primes; int read() { int x; cin x; return x; } // 计算单组答案 int calc(int n) { mapint, int sum_exp; setint 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不是统计数字出现次数简单版 (x1)输入的 x 不需要参与任何计算模数 (10^97) 不要写错。