資料結構
網路
關係資料庫管理系統 (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 次瀏覽
