这是 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
```

该解法能高效通过大数据范围约束。

 

Logo

汇聚全球AI编程工具,助力开发者即刻编程。

更多推荐