如何找到该子数组的乘积具有奇数除数的子数组的计数？

Question

我考试时也遇到过这个问题，但我无法解决。

任何小于 O(n2) 时间复杂度的答案都可以。

ex- array = [4,3,12] all sub-arrays = [4], [3], [12], [4,3], [3,12], [4,3,12] expected ans - [4], [4,3,12]

1 <= array length <= 2*10^5

1 <= array[i] <= 200

我是在公司平台上做的，所以我现在没有代码，但它没有通过所有测试用例，其中一些是 TLE。

Answer 1

回想一下，可以通过求质因数分解来计算正整数的因子数，然后将每个因子的重数的乘积加 1。由于偶数与另一个整数的乘积始终是偶数，因此该乘积为奇数，所有重数必须为偶数。

首先，创建一个字典，将每个质因数的奇偶校验数组（0 表示偶数，1 表示奇数）映射到一个计数，并使用频率为 1 的全 0 数组（第一个数组元素之前的点）进行初始化。由于所有数组元素都在 1 到 200 之间，因此我们只需要每个状态一个大小为 200 的数组，即 O(1)。

在求子数组的乘积时，我们将质因数计数相加。如果我们考虑一个前缀和数组，[l, r] 之间的子数组中每个素因子的频率就是 r 和 l - 1 之间的累积频率之差。

现在，在迭代输入时维护每个质因数的奇偶校验的累积数组。用当前元素更新奇偶校验数组后，我们尝试将当前索引作为子数组的右端点

r

，并查找匹配的索引数量

l - 1

。该指数的质因数的累积奇偶性应该与当前的累积奇偶性相同，因为减去两个奇数或两个偶数会产生偶数。因此，我们使用当前奇偶校验数组作为键来访问字典，并将值添加到结果中。然后，我们增加字典中当前奇偶校验数组的值以供以后迭代。

这可能是

O(N)

（预期）或

O(N log N)

，具体取决于字典实现。