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

2023-06-21 13:04:03 176

给定一个数组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(intarr[],intsize,intk)接受一个数组和k并返回其乘积可被k整除的子数组的计数。

将初始计数作为输入。

从i=0到i

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

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

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

有效的方法

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

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

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

函数set_in(intfit,intfirst,intlast,constint*arr,intk)用于构建产品的段树。

函数check(intfit,intfirst,intlast,intstart,intend,intk)用于查找子数组在开始和结束之间的乘积。

如果first>last或first>end或last

如果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(intarr[],intsize,intk)接受arr[]和k并返回乘积可被k整除的子数组的计数。

取初始计数为0。

将初始计数设置为0。

使用两个for循环从i=0到i

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

返回计数作为最终结果。

示例

#include 
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: "<输出结果
如果我们运行上面的代码，它将生成以下输出-
Count of sub−arrays whose product is divisible by k are: 18
Example(EfficientApproach)
#include 
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: "<输出结果
如果我们运行上面的代码，它将生成以下输出-
Count of sub−arrays whose product is divisible by k are: 18

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

输入

解释

输入

解释

天真的方法

有效的方法

示例

Example(EfficientApproach)

热门推荐

随机推荐