Count sub | JavaScript implementation for above 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
let MAX = 100002 ; let tree = new Array ( 4 * MAX ) ; function build ( node , start , end , arr , k ) { if ( start == end ) { tree [ node ] = ( 1 * arr [ start ] ) % k ; return ; } let 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 ; } function query ( node , start , end , l , r , k ) { if ( start > end start > r end < l ) { return 1 ; } if ( start >= l && end <= r ) { return tree [ node ] % k ; } let mid = ( start + end ) >> 1 ; let q1 = query ( 2 * node , start , mid , l , r , k ) ; let q2 = query ( 2 * node + 1 , mid + 1 , end , l , r , k ) ; return ( q1 * q2 ) % k ; } function countSubarrays ( arr , n , k ) { let count = 0 ; for ( let i = 0 ; i < n ; i ++ ) { for ( let j = i ; j < n ; j ++ ) { let product_mod_k = query ( 1 , 0 , n - 1 , i , j , k ) ; if ( product_mod_k == 0 ) { count ++ ; } } } return count ; } let arr = [ 6 , 2 , 8 ] ; let n = arr . length ; let k = 4 ; build ( 1 , 0 , n - 1 , arr , k ) ; document . write ( countSubarrays ( arr , n , k ) ) ;