在 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
