Count sub | Python3 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
MAX = 100002 NEW_LINE tree = [ 0 for i in range ( 4 * MAX ) ] ; NEW_LINE def build ( node , start , end , arr , k ) : NEW_LINE INDENT if ( start == end ) : NEW_LINE INDENT tree [ node ] = ( arr [ start ] ) % k ; NEW_LINE return ; NEW_LINE DEDENT mid = ( start + end ) >> 1 ; NEW_LINE build ( 2 * node , start , mid , arr , k ) ; NEW_LINE build ( 2 * node + 1 , mid + 1 , end , arr , k ) ; NEW_LINE tree [ node ] = ( tree [ 2 * node ] * tree [ 2 * node + 1 ] ) % k ; NEW_LINE DEDENT def query ( node , start , end , l , r , k ) : NEW_LINE INDENT if ( start > end or start > r or end < l ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT if ( start >= l and end <= r ) : NEW_LINE INDENT return tree [ node ] % k ; NEW_LINE DEDENT mid = ( start + end ) >> 1 ; NEW_LINE q1 = query ( 2 * node , start , mid , l , r , k ) ; NEW_LINE q2 = query ( 2 * node + 1 , mid + 1 , end , l , r , k ) ; NEW_LINE return ( q1 * q2 ) % k ; NEW_LINE DEDENT def countSubarrays ( arr , n , k ) : NEW_LINE INDENT count = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( i , n ) : NEW_LINE INDENT product_mod_k = query ( 1 , 0 , n - 1 , i , j , k ) ; NEW_LINE if ( product_mod_k == 0 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 6 , 2 , 8 ] NEW_LINE n = len ( arr ) NEW_LINE k = 4 ; NEW_LINE build ( 1 , 0 , n - 1 , arr , k ) ; NEW_LINE print ( countSubarrays ( arr , n , k ) ) NEW_LINE DEDENT