求子数组最小公倍数中质因子数数目之和

首先，我们需要知道一个结论：一个数的质因子数目等于其所有质因子的指数之和加1。比如，$24=2^3\times3$，其质因子数目为$3+1=4$。

接下来，我们可以使用暴力枚举子数组的方法，对每个子数组求出其最小公倍数，然后计算其质因子数目之和即可。时间复杂度为$O(n^3)$，其中$n$为数组长度，由于子数组数量为$O(n^2)$，对每个子数组求最小公倍数的时间复杂度为$O(n)$。

代码如下：

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

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

def count_factors(num):
    count = 0
    for i in range(2, int(num**0.5)+1):
        while num % i == 0:
            count += 1
            num //= i
    if num > 1:
        count += 1
    return count

def subarray_lcm_factor_sum(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        for j in range(i, n):
            subarr_lcm = arr[i]
            for k in range(i+1, j+1):
                subarr_lcm = lcm(subarr_lcm, arr[k])
            ans += count_factors(subarr_lcm)
    return ans

然而，上述方法的时间复杂度较高，不能通过本题。考虑优化。

观察题目的数据范围，发现数组中每个元素都小于$10^6$，因此一个子数组的最小公倍数也不可能超过$10^6$，这启示我们可以对每个质数预处理出其在$[1,10^6]$范围内的倍数中出现的次数。具体地，我们可以使用线性筛法预处理出所有小于等于$10^6$的质数，然后对每个质数$p$，预处理出其在$[1,10^6]$范围内的倍数中出现的次数$cnt_p$，即：

$$cnt_p=\sum_{i=1}^{\lfloor 10^6/p\rfloor}\lfloor\frac{i}{p}\rfloor$$

这里的$\lfloor x\rfloor$表示不超过$x$的最大整数。例如，当$p=2$时，有$cnt_2=\lfloor 10^6/2\rfloor+\lfloor 10^6/4\rfloor+\lfloor 10^6/8\rfloor+\cdots=500000+250000+125000+\cdots$。这个式子可以用等比数列求和公式简化为$cnt_2=10^6-1$。

预处理完成后，对于每个子数组，我们可以依次枚举$[1,10^6]$范围内的质数$p$，统计其在子数组的最小公倍数中出现的次数。具体地，设当前枚举到的质数为$p$，统计$p^{cnt_p}$在子数组的最小公倍数中出现的次数。这个数量等于子数组中所有元素中$p$的指数的最小值乘以$cnt_p$。

具体地，我们可以用一个长度为$10^6+1$的数组$factor$来存储每个数对应的最小质因子。我们可以先用线性筛法求出所有小于等于$10^6$的质数，并将它们的倍数都标记上最小质因子。然后，对于每个子数组，我们可以使用一个长度为$10^6+1$的数组$cnt$来统计每个质数的指数之和，然后根据上述公式计算质因子数目之和。

总时间复杂度为$O(n\log\log 10^6)$，其中$n$为数组长度。

代码如下：

def subarray_lcm_factor_sum(arr):
    n = len(arr)
    # 预处理每个数的最小质因子
    factor = [0] * (10**6+1)
    primes = []
    for i in range(2, 10**6+1):
        if factor[i] == 0:
            factor[i] = i
            primes.append(i)
        for p in primes:
            if p > factor[i] or i*p > 10**6:
                break
            factor[i*p] = p
    # 预处理每个质数在[1,10^6]范围内的倍数中出现的次数
    cnt = [0] * (10**6+1)
    for p in primes:
        cnt[p] = 10**6 // p
        for i in range(2, cnt[p]+1):
            cnt[p] -= cnt[i*p]
    # 枚举子数组，统计质因子数目之和
    ans = 0
    for i in range(n):
        for j in range(i, n):
            subarr_lcm = arr[i]
            for k in range(i+1, j+1):
                subarr_lcm = lcm(subarr_lcm, arr[k])
            for p in primes:
                if p > subarr_lcm:
                    break
                exp_sum = float('inf')
                for x in arr[i:j+1]:
                    exp_sum = min(exp_sum, get_exponent(x, p))
                ans += exp_sum * cnt[p]
    return ans

其中，$get\_exponent(x,p)$用于计算$x$在质因数分解中$p$的指数，代码如下：

def get_exponent(num, prime):
    exp = 0
    while num % prime == 0:
        exp += 1
        num //= prime
    return exp