数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究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。
如果乘积temp可以被k整除，则递增计数。
在所有三个循环结束时，返回计数作为结果。
高效方法
在这种方法中，我们将产品存储在段树中，而不是遍历每个子数组。现在使用段树中可被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)用于查找start和end之间的子数组的乘积。
如果first>last或first>end或last<start，则返回1。
如果first>=last且last<=end，则返回arr_2[fir]%k。
设置level=first+last >> 1（除以2）。
现在对level和level+1递归调用check()并将结果存储在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)。
如果此temp为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
270 次浏览
