Count of elements having odd number of divisors in index range [ L , R ] for Q queries | Python3 program for the above approach ; Function count the number of elements having odd number of divisors ; Initialise dp [ ] array ; Precomputation ; Find the Prefix Sum ; Iterate for each query ; Find the answer for each query ; Driver code ; Given array arr [ ] ; Given Query ; Function call
import math NEW_LINE def OddDivisorsCount ( n , q , a , Query ) : NEW_LINE INDENT DP = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT x = int ( math . sqrt ( a [ i ] ) ) ; NEW_LINE if ( x * x == a [ i ] ) : NEW_LINE INDENT DP [ i ] = 1 ; NEW_LINE DEDENT DEDENT for i in range ( 1 , n ) : NEW_LINE INDENT DP [ i ] = DP [ i - 1 ] + DP [ i ] ; NEW_LINE DEDENT l = 0 NEW_LINE r = 0 NEW_LINE for i in range ( q ) : NEW_LINE INDENT l = Query [ i ] [ 0 ] ; NEW_LINE r = Query [ i ] [ 1 ] ; NEW_LINE if ( l == 0 ) : NEW_LINE INDENT print ( DP [ r ] ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( DP [ r ] - DP [ l - 1 ] ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 5 ; NEW_LINE Q = 3 ; NEW_LINE arr = [ 2 , 4 , 5 , 6 , 9 ] NEW_LINE Query = [ [ 0 , 2 ] , [ 1 , 3 ] , [ 1 , 4 ] ] NEW_LINE OddDivisorsCount ( N , Q , arr , Query ) ; NEW_LINE DEDENT