题目描述

给定一个整数数组 nums，小李想将 nums 切割成若干个非空子数组，使得每个子数组最左边的数和最右边的数的最大公约数大于 1。为了减少他的工作量，请求出最少可以切成多少个子数组。

样例

输入：nums = [2,3,3,2,3,3]
输出：2
解释：最优切割为 [2,3,3,2] 和 [3,3]。
第一个子数组头尾数字的最大公约数为 2，第二个子数组头尾数字的最大公约数为 3。

输入：nums = [2,3,5,7]
输出：4
解释：只有一种可行的切割：[2], [3], [5], [7]。

限制

• 1 <= nums.length <= 10^5
• 2 <= nums[i] <= 10^6

算法

(动态规划，数学) $O(S + n\frac{\sqrt S}{\log S})$

1. 设状态 $f(i)$ 表示前 $i$ 个数字，最少可以切分成多少个子数组。
2. 初始时 $f(0) = 0$，其余待定。
3. 转移时，暴力来看，直接枚举 $1 \le j \le i$，如果满足 $gcd(nums(i), nums(j)) > 1$，则转移 $f(i) = \min(f(i), f(j - 1) + 1)$。
4. 但暴力转移会超时，需要优化。
5. 尝试从 $S$ 的质因数下手，如果我们拿到 $S$ 的质因数，且一直这些质因数对应转移的最小值，就可以进行转移了。令 $g(j)$ 表示第 $j$ 个质数中所对应转移的最小值。例如 $g(0)$ 就是质数 2 对应的最小转移值。如果 $nums(i)$ 中含有 2 作为质因数，则先更新 $g(0) = \min(g(0), f(i - 1))$，然后更新 $f(i) = \min(f(i), g(0) + 1)$，对于其他质因数同样处理。
6. 接下来问题变成了如何快速求质因数。
7. 先通过线性筛求出所有的质数，并且建立质数到排名的映射 idx。
8. 若求 x 的质因数，在 x 不是质数的情况下，遍历质数试除。
9. 最终答案为 $f(n)$。

时间复杂度

• 线性筛求质数的时间复杂度为 $O(S)$，其中 $S$ 为最大的数。
• 质因数的个数最多有 $O(\log S)$ 个，但最坏情况下，$S$ 是两个 $\sqrt S$ 的质数乘积，此时需要遍历从 $2$ 到 $\sqrt S$ 这么多的质数。前 $S$ 个数的质数个数大概有 $O(\frac{S}{\log S})$，所以最坏情况下，需要 $O(\frac{\sqrt S }{\log S})$ 的时间找到所有质因数。
• 动态规划的状态数为 $O(n)$，每次转移时间等于找质因数的时间。
• 故总时间复杂度为 $O(S + n\frac{\sqrt S}{\log S})$。

空间复杂度

• 需要 $O(n + S)$ 的空间存储动态规划的状态，以及质数的相关信息。

C++ 代码

#define N 100010
#define M 1000010
#define INF 1000000000

class Solution {
private:
    int prime[M], cnt;
    int idx[M];

    int f[N], g[M];

    void init() {
        const int m = 1000000;
        memset(idx, 0, sizeof(idx));

        cnt = 0;
        for (int i = 2; i <= m; i++) {
            if (idx[i] == 0)
                prime[cnt++] = i;

            for (int j = 0; j < cnt && i * prime[j] <= m; j++) {
                idx[i * prime[j]] = -1;
                if (i % prime[j] == 0)
                    break;
            }
        }

        for (int i = 0; i < cnt; i++) {
            idx[prime[i]] = i;
            g[i] = INF;
        }
    }

    int min(int x, int y) {
        return x < y ? x : y;
    }

public:
    int splitArray(vector<int>& nums) {
        const int n = nums.size();
        init();

        f[0] = 0;
        for (int i = 1; i <= n; i++) {
            f[i] = f[i - 1] + 1;
            int x = nums[i - 1];

            for (int j = 0; j < cnt && x > 1 && idx[x] == -1; j++) {
                if (x % prime[j] == 0) {
                    g[j] = min(g[j], f[i - 1]);
                    f[i] = min(f[i], g[j] + 1);
                }

                while (x % prime[j] == 0)
                    x /= prime[j];
            }

            if (x > 1) {
                g[idx[x]] = min(g[idx[x]], f[i - 1]);
                f[i] = min(f[i], g[idx[x]] + 1);
            }
        }

        return f[n];
    }
};