乘积不能被k整除的子数组数

Question

给定一个数组，我想计算子数组的数量（连续的），当取的乘积不会被k整除。

例如。设 A = [1， 2， 3， 4， 5， 6] 和 K = 2

则使乘积不能被 K 整除的子数组数为 2：

{1}
{3}
{5}

其余的都可以被2整除。

{1, 2}
{1, 2, 3}
{1, 2, 3, 4}
{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5, 6}
{2}
{2, 3}
{2, 3, 4}
{2, 3, 4, 5} etc..

我首先尝试计算子数组（n）（n 1）/2的总数，然后使用mod减去可被k整除的子数组的数量，但它不起作用。我该如何解决这个问题？

这（错误地）计算了乘积可被K整除的子阵列数：

int curr = 1;
    int x = 0;
    for (int i = 0; i < a.length; i++) {
        curr = curr * a[i] % k;
        if (curr == 0) {
            curr = 1;
            if (x > 0)
                ans = ans.subtract(NumberUtils.nChooseR(x + 1, 2));
            if (a[i] % k != 0) {
                x = 1;
            } else {
                x = 0;
            }
        } else {
            x++;
        }
    }
    if (x != 0) {
        ans = ans.subtract(NumberUtils.nChooseR(x + 1, 2));
    }
    return ans;

一个稍微相关的问题是这个问题，但它涉及加法，因此不能在这里应用。

编辑：对数组大小的约束是10^5，对数组元素的限制是10^9。因此，我正在寻找线性或线性时间的解决方案

Answer 1

“大局”：

>

很容易看出，如果 [l， r] 子数组积可被 K 整除，则 [l， r 1] 和 [l - 1， r] 的乘积也是如此。

因此，如果我们可以有效地计算子数组模K的乘积的值，我们可以只移动两个指针（左指针正好向右移动一个，右指针不断增加，直到乘积等于零模K）。这样，我们将获得从左指针位置开始且其积可被K整除的子数组的数量。答案将只是左指针所有值的总和。

问题：我们无法显式存储产品（它太大）。我们也不能做模运算，因为移动左指针需要模除法。我们可能没有反比。

解决方案1:

让我们用一棵段树来计算任意子阵列在< code>O(log N)时间内的模K的乘积(我们只需构建树，并在每个节点中存储对应范围模K的乘积。现在我们只需要将查询范围分解成的所有节点的这些值相乘(模K)。我们可以使用两个指针，因为我们可以有效地计算任何子数组模K的乘积。

解决方案2:

分而治之。

让我们将数组分成两个（几乎）相等的部分，并递归地解决每个部分的问题。现在我们只需要计算从前半部分开始并以第二部分结束的好子数组的数量。但是每个这样的子数组的乘积是[l， m]和[m 1， r]部分的乘积（所有计算都是模K完成的）。但是m是固定的（它是拆分数组的位置）。因此，我们可以在线性时间内为所有l预计算[l， m]的乘积，为所有r预计算[m 1， r]的乘积。现在我们可以再次使用两个指针（它们分别用0和m 1初始化）。我们可以在线性时间内“合并”两半，因此总时间复杂度再次为O（N log N）。