求子数组最小公倍数中质因子数数目之和c++代码

首先，我们可以通过暴力枚举所有子数组，并对每个子数组求最小公倍数，然后再统计质因子数目之和。

代码如下：

def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)

def lcm(a, b):
    return a * b // gcd(a, b)

def factor_count(n):
    count = 0
    i = 2
    while i * i <= n:
        if n % i == 0:
            count += 1
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        count += 1
    return count

def subarray_lcm_factor_count(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        for j in range(i, n):
            lcm_val = arr[i]
            for k in range(i + 1, j + 1):
                lcm_val = lcm(lcm_val, arr[k])
            ans += factor_count(lcm_val)
    return ans

但是，这个算法的时间复杂度是 $O(n^3 \log m)$，其中 $m$ 是数组中的最大值。对于较大的数据集，这个算法显然不可行。

因此，我们需要寻找更高效的算法。我们可以考虑先对数组进行预处理，计算出每个位置的最小公倍数，然后通过这些信息来计算子数组的最小公倍数以及质因子数目之和。

具体来说，我们可以使用一个二维数组 $dp$ 来预处理最小公倍数，其中 $dp_{i,j}$ 表示以位置 $i$ 开始、长度为 $2^j$ 的子数组的最小公倍数。状态转移方程如下：

$$
dp_{i,j} = \text{lcm}(dp_{i,j-1}, dp_{i+2^{j-1},j-1})
$$

同时，我们可以再使用一个二维数组 $f$ 来预处理质因子数目之和，其中 $f_{i,j}$ 表示以位置 $i$ 开始、长度为 $2^j$ 的子数组的质因子数目之和。状态转移方程如下：

$$
f_{i,j} = f_{i,j-1} + f_{i+2^{j-1},j-1} - f_{i,j-1} \times f_{i+2^{j-1},j-1}
$$

这个方程的含义是，将一个长度为 $2^j$ 的子数组拆分成两个长度为 $2^{j-1}$ 的子数组，分别计算它们的质因子数目之和，然后将它们合并起来，避免重复计算。

最终，我们可以通过下面的代码来实现这个算法：

def subarray_lcm_factor_count(arr):
    n = len(arr)
    max_pow = int(math.log2(n)) + 1
    dp = [[0] * max_pow for _ in range(n)]
    for i in range(n):
        dp[i][0] = arr[i]
    for j in range(1, max_pow):
        for i in range(n - 2 ** j + 1):
            dp[i][j] = lcm(dp[i][j - 1], dp[i + 2 ** (j - 1)][j - 1])
    f = [[0] * max_pow for _ in range(n)]
    for i in range(n):
        f[i][0] = factor_count(arr[i])
    for j in range(1, max_pow):
        for i in range(n - 2 ** j + 1):
            f[i][j] = f[i][j - 1] + f[i + 2 ** (j - 1)][j - 1] - f[i][j - 1] * f[i + 2 ** (j - 1)][j - 1]
    ans = 0
    for j in range(max_pow):
        for i in range(n - 2 ** j + 1):
            ans += f[i][j]
            lcm_val = dp[i][j]
            for k in range(j - 1, -1, -1):
                if i + 2 ** k <= n - 2 ** j:
                    lcm_val = lcm(lcm_val, dp[i + 2 ** k][k])
            ans += factor_count(lcm_val)
    return ans

这个算法的时间复杂度为 $O(n \log n)$，可以通过本题。