约数相关

枚举约数

• 对于 \(n \le 10^9\)，具有最多约数的 \(n=735134400\)，共有 \(1344\) 个约数。

设一个数为 \(n\)，对于 \(n \ge 1260\)，其约数不超过 \(\sqrt{n}\)。只枚举约数能极大的减少时间复杂度。 放上一段枚举约数的代码：

    for(int i = 1; i * i <= num; i++){
        if(num % i) continue;
        if(check(i) || check(num / i)){ // 注意要处理两个
            flag = true;
            break;
        }
    }

注意枚举大于 \(num\) 的数字！

阶乘约数

例题

给定一个数 \(n\)，求出 \(n!\) 的约数个数。

根据约数个数的计算方法，我们可以将其转换为一个子问题：

对于一个质数 \(p\)，求出 \(n!\) 中 \(p\) 的指数。

我们发现，所有 \(kp\le n\) 的 \(kp\) 会对指数造成 \(1\) 的贡献，而剩下的 \(kp^2\le n\) 会对指数造成额外 \(1\) 的贡献，\(kp^3\le n!\) 会对指数另造成 \(1\) 的贡献……因此，\(n\) 中 \(p\) 的指数可以表示为：

\[ k=\sum_{i=1}^{p^i\le n}{\lfloor\frac{n}{p^i}\rfloor} \]

此方法可以在 \(O(\log_p{n})\) 的时间复杂度内求出 \(n\) 中 \(p\) 的次数。

再搭配线性筛，筛出小于等于 \(n\) 的所有质数，求出其在 \(n!\) 中的次数 \(k_i\)，那么 \(n!\) 的约数个数就为 \(\prod{(k_i+1)}\)。

本算法具有玄学时间复杂度。