DeepSeek LeetCode 2338.统计理想数组的数目 JavaScript实现
这是 LeetCode 2338「统计理想数组的数目」的 JavaScript 实现，主要利用质因数分解 + 组合数学（隔板法）来解决。
```javascript
/**
* @param {number} n
* @param {number} maxValue
* @return {number}
*/
const idealArrays = (n, maxValue) => {
const MOD = 1e9 + 7;
const limit = maxValue;
// 预处理组合数 C(n+k-1, k)
// 我们需要计算 C(n + len - 1, len)
// 因为 n 最大 1e4，这里 n + 最大指数和大约 2e4
const maxLen = 14; // 2^14 = 16384 > 1e4
const 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[i+1]) * BigInt(i+1)) % 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);
}
// 如果没有质因子（num=1），指数数组为空
// 对于空数组，C(n+0-1,0)=1
let ways = 1n;
for (const e of exponents) {
// 指数 e 在长度为 n 的数组中非递减（实际是递增，因为必须整除，但指数可以相等）
// 把 e 个相同的球放入 n 个盒子（允许空盒）=> C(n+e-1, e)
ways = ways * BigInt(comb(n + e - 1, e)) % BigInt(MOD);
}
total = (total + ways) % BigInt(MOD);
}
return Number(total);
};
```
核心思路
1. 问题转化
理想数组满足 arr[i] | arr[i+1]（整除）。把每个数用质因数分解表示：
arr[i] = p1^{a_i1} p2^{a_i2} ...
则整除条件等价于每个质因子的指数序列是非递减的。
2. 独立计数
不同质因子独立，对于每个质因子的指数序列，长度为 n，从 0 到某个最大值 e（目标数的指数），求非递减序列个数。
这等价于：把 e 个相同小球放入 n 个盒子（允许空） = C(n+e-1, e)。
3. 组合数计算
n 最大 1e4，指数 e 最大约 log₂(maxValue) ≤ 14，因此 n+e-1 ≤ 10013，可直接预处理阶乘和逆元。
4. 遍历 1..maxValue
对每个数质因数分解，得到各质因子指数，将每个指数对应的组合数相乘，累加所有数的结果。
时间复杂度
· 预处理阶乘、逆元：O(n + log MOD)
· 每个数质因数分解：O(log maxValue)
· 总复杂度：O(maxValue log maxValue)
示例
```javascript
console.log(idealArrays(2, 5)); // 10
console.log(idealArrays(5, 3)); // 11
```
该解法能高效通过大数据范围约束。