这是 LeetCode 2338「统计理想数组的数目」的 JavaScript 实现主要利用质因数分解 组合数学隔板法来解决。javascript/*** param {number} n* param {number} maxValue* return {number}*/const idealArrays (n, maxValue) {const MOD 1e9 7;const limit maxValue;// 预处理组合数 C(nk-1, k)// 我们需要计算 C(n len - 1, len)// 因为 n 最大 1e4这里 n 最大指数和大约 2e4const maxLen 14; // 2^14 16384 1e4const maxComputed n maxLen;// 阶乘与逆元const fact new Array(maxComputed 5);const invFact new Array(maxComputed 5);fact[0] 1;for (let i 1; i maxComputed; i) {fact[i] Number((BigInt(fact[i-1]) * BigInt(i)) % BigInt(MOD));}// 快速幂const powMod (a, b) {let res 1n;let base BigInt(a);let exp b;while (exp 0) {if (exp 1) res (res * base) % BigInt(MOD);base (base * base) % BigInt(MOD);exp 1;}return Number(res);};invFact[maxComputed] powMod(fact[maxComputed], MOD-2);for (let i maxComputed-1; i 0; i--) {invFact[i] Number((BigInt(invFact[i1]) * BigInt(i1)) % BigInt(MOD));}const comb (a, b) {if (b 0 || b a) return 0;let res BigInt(fact[a]) * BigInt(invFact[b]) % BigInt(MOD);res res * BigInt(invFact[a-b]) % BigInt(MOD);return Number(res);};// 对 1..maxValue 做质因数分解记录每个数的质因数分解指数形式// 但是不需要所有数我们只需要对于每个数分解为 p1^e1 * p2^e2 * ...// 然后对于每个质因子的指数序列求非递减序列个数 C(n len(e) - 1, len(e))乘起来let total 0n;// 预处理最小质因子用于快速分解const spf new Array(limit 1);for (let i 2; i limit; i) {if (!spf[i]) {spf[i] i;for (let j i*i; j limit; j i) {if (!spf[j]) spf[j] i;}}}for (let i 2; i limit; i) {if (!spf[i]) spf[i] i;}// 对每个数分解质因数得到指数数组for (let num 1; num limit; num) {let x num;const exponents [];while (x 1) {const p spf[x];let cnt 0;while (x % p 0) {x / p;cnt;}exponents.push(cnt);}// 如果没有质因子num1指数数组为空// 对于空数组C(n0-1,0)1let ways 1n;for (const e of exponents) {// 指数 e 在长度为 n 的数组中非递减实际是递增因为必须整除但指数可以相等// 把 e 个相同的球放入 n 个盒子允许空盒 C(ne-1, e)ways ways * BigInt(comb(n e - 1, e)) % BigInt(MOD);}total (total ways) % BigInt(MOD);}return Number(total);};核心思路1. 问题转化理想数组满足 arr[i] | arr[i1]整除。把每个数用质因数分解表示arr[i] p1^{a_i1} p2^{a_i2} ...则整除条件等价于每个质因子的指数序列是非递减的。2. 独立计数不同质因子独立对于每个质因子的指数序列长度为 n从 0 到某个最大值 e目标数的指数求非递减序列个数。这等价于把 e 个相同小球放入 n 个盒子允许空 C(ne-1, e)。3. 组合数计算n 最大 1e4指数 e 最大约 log₂(maxValue) ≤ 14因此 ne-1 ≤ 10013可直接预处理阶乘和逆元。4. 遍历 1..maxValue对每个数质因数分解得到各质因子指数将每个指数对应的组合数相乘累加所有数的结果。时间复杂度· 预处理阶乘、逆元O(n log MOD)· 每个数质因数分解O(log maxValue)· 总复杂度O(maxValue log maxValue)示例javascriptconsole.log(idealArrays(2, 5)); // 10console.log(idealArrays(5, 3)); // 11该解法能高效通过大数据范围约束。