在 C++ 中计算乘积可被 k 整除的子数组

给定一个数组 arr[] 和一个整数 k 作为输入。目标是找到 arr[] 的子数组的数量,使得该子数组的元素的乘积可以被 k 整除。

例如

输入

arr[] = {2, 1, 5, 8} k=4
输出结果
Count of sub-arrays whose product is divisible by k are: 4

解释

The subarrays will be:

[ 8 ], [ 5,8 ], [ 1,5,8 ], [ 2,1,5,8 ].

输入

arr[] = {7,1,9,7} k=9
输出结果
Count of sub−arrays whose product is divisible by k are: 6

解释

The subarrays will be:

[ 9 ], [ 9,7 ], [ 1,9 ], [ 1,9,7 ], [ 7,1,9 ], [ 7,1,9,7 ].

以下程序中使用的方法如下-

天真的方法

我们将使用两种方法解决这个问题。在朴素的方法中,简单地使用两个 for 循环遍历数组,并且对于索引 i 和 j 之间的每个子数组,检查元素的乘积是否可以被 k 整除。如果是,则增加计数。

  • 以整数数组 arr[] 和 k 作为输入。

  • 函数 product_k(int arr[], int size, int k) 接受一个数组和 k 并返回其乘积可被 k 整除的子数组的计数。

  • 将初始计数作为输入。

  • 从 i=0 到 i<size 和 j=i 到 j<size 遍历 arr。并且 k=i 到 k<=j

  • 对于每个子数组 arr[ i 到 j ],将 arr[k] 乘以 temp。

  • 如果产品温度可被 k 整除,则增加计数。

  • 在所有三个循环结束时,返回计数作为结果。

有效的方法

W在这种方法中,我们将把乘积存储在段树中,而不是遍历每个子数组。现在使用这棵树中可被 k 整除的乘积。并相应地增加计数。

  • 以整数数组 arr[] 和 k 作为输入。

  • 我们将段树实现为数组 arr_2[4 * size_2]。

  • 函数 set_in(int fit, int first, int last, const int* arr, int k) 用于构建产品的段树。

  • 函数check(int fit, int first, int last, int start, int end, int k)用于查找子数组在开始和结束之间的乘积。

  • 如果 first>last 或 first>end 或 last<start 返回 1。

  • 如果 first>=last 和 last<=end 则返回 arr_2[fir]%k。

  • 设置 level=first+last >> 1 (除以 2 )。

  • 现在递归调用check()level 和 level+1 并存储在 set_1 和 set_2 中。

  • 设置 count=set_1+set_2 并返回 count。

  • 函数 product_k(int arr[], int size, int k) 接受 arr[] 和 k 并返回乘积可被 k 整除的子数组的计数。

  • 取初始计数为 0。

  • 将初始计数设置为 0。

  • 使用两个 for 循环从 i=0 到 i<size 和 j=0 到 j<size 进行遍历。设置 temp=check(1, 0, size − 1, i, j, k)。

  • 如果此温度为 0,则增加计数。

  • 返回计数作为最终结果。

示例

#include <bits/stdc++.h>

using namespace std;

int product_k(int arr[], int size, int k){

   int count = 0;

   for (int i = 0; i < size; i++){

      for (int j = i; j < size; j++){

         int temp = 1;

         for (int k = i; k <= j; k++){

            temp = temp * arr[k];

         }

         if(temp % k == 0){

            count++;

         }

      }

   }

   return count;

}

int main(){

   int arr[] = {2, 1, 5, 8, 10, 12 };

   int size = sizeof(arr) / sizeof(arr[0]);

   int k = 2;

   cout<<"Count of sub−arrays whose product is divisible by k are: "<<product_k(arr, size, k);

   return 0;

}

输出结果

如果我们运行上面的代码,它将生成以下输出 -

Count of sub−arrays whose product is divisible by k are: 18

Example(Efficient Approach)

#include <bits/stdc++.h>

using namespace std;

#define size_2 100002

int arr_2[4 * size_2];

void set_in(int fit, int first, int last, const int* arr, int k){

   if (first == last){

      arr_2[fit] = (1LL * arr[first]) % k;

      return;

   }

   int level = (first + last) >> 1;

   set_in(2 * fit, first, level, arr, k);

   set_in(2 * fit + 1, level + 1, last, arr, k);

   arr_2[fit] = (arr_2[2 * fit] * arr_2[2 * fit + 1]) % k;

}

int check(int fit, int first, int last, int start, int end, int k){

   if(first > last){

      return 1;

   }

   if(first > end){

      return 1;

   }

   if(last < start){

      return 1;

   }

   if (first >= start){

      if(last <= end){

         return arr_2[fit] % k;

      }

   }

   int level = (first + last) >> 1;

   int set_1 = check(2 * fit, first, level, start, end, k);

   int set_2 = check(2 * fit + 1, level + 1, last, start, end, k);

   int count = (set_1 * set_2) % k;

   return count;

}

int product_k(int arr[], int size, int k){

   int count = 0;

   for (int i = 0; i < size; i++){

      for (int j = i; j < size; j++){

         int temp = check(1, 0, size − 1, i, j, k);

         if (temp == 0){

            count++;

         }

      }

   }

   return count;

}

int main(){

   int arr[] = {2, 1, 5, 8, 10, 12};

   int size = sizeof(arr) / sizeof(arr[0]);

   int k = 2;

   set_in(1, 0, size − 1, arr, k);

   cout<<"Count of sub−arrays whose product is divisible by k are: "<<product_k(arr, size, k);

   return 0;

}

输出结果

如果我们运行上面的代码,它将生成以下输出 -

Count of sub−arrays whose product is divisible by k are: 18

以上是 在 C++ 中计算乘积可被 k 整除的子数组 的全部内容, 来源链接: utcz.com/z/359928.html

回到顶部