给定一个数组 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
#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