Count sub | C ++ implementation of the approach ; Segment tree implemented as an array ; Function to build the segment tree ; Function to query product of sub - array [ l . . r ] in O ( log n ) time ; Function to count sub - arrays whose product is divisible by K ; Query segment tree to find product % k of the sub - array [ i . . j ] ; Driver code ; Build the segment tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE #define MAX  100002 NEW_LINE ll tree [ 4 * MAX ] ; void build ( int node , int start , int end , const int * arr , int k ) { if ( start == end ) { tree [ node ] = ( 1LL * arr [ start ] ) % k ; return ; } int mid = ( start + end ) >> 1 ; build ( 2 * node , start , mid , arr , k ) ; build ( 2 * node + 1 , mid + 1 , end , arr , k ) ; tree [ node ] = ( tree [ 2 * node ] * tree [ 2 * node + 1 ] ) % k ; } ll query ( int node , int start , int end , int l , int r , int k ) { if ( start > end start > r end < l ) { return 1 ; } if ( start >= l && end <= r ) { return tree [ node ] % k ; } int mid = ( start + end ) >> 1 ; ll q1 = query ( 2 * node , start , mid , l , r , k ) ; ll q2 = query ( 2 * node + 1 , mid + 1 , end , l , r , k ) ; return ( q1 * q2 ) % k ; } ll countSubarrays ( const int * arr , int n , int k ) { ll count = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i ; j < n ; j ++ ) { ll product_mod_k = query ( 1 , 0 , n - 1 , i , j , k ) ; if ( product_mod_k == 0 ) { count ++ ; } } } return count ; } int main ( ) { int arr [ ] = { 6 , 2 , 8 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int k = 4 ; build ( 1 , 0 , n - 1 , arr , k ) ; cout << countSubarrays ( arr , n , k ) ; return 0 ; }