Count sequences of length K having each term divisible by its preceding term | Stores the factors of i - th element in v [ i ] ; Function to find all the factors of N ; Iterate upto sqrt ( N ) ; Function to return the count of sequences of length K having all terms divisible by its preceding term ; Calculate factors of i ; Initialize dp [ 0 ] [ i ] = 0 : No subsequence of length 0 ending with i - th element exists ; Initialize dp [ 0 ] [ i ] = 1 : Only 1 subsequence of length 1 ending with i - th element exists ; Iterate [ 2 , K ] to obtain sequences of each length ; Calculate sum of all dp [ i - 1 ] [ vp [ j ] [ k ] ] ; vp [ j ] [ k ] stores all factors of j ; Store the sum in A [ i ] [ j ] ; Sum of all dp [ K ] [ j ] obtain all K length sequences ending with j ; Driver code
vp = [ [ ] for i in range ( 2009 ) ] NEW_LINE def finding_factors ( n ) : NEW_LINE INDENT i = 1 NEW_LINE a = 0 NEW_LINE global vp NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT if ( i * i == n ) : NEW_LINE INDENT vp [ n ] . append ( i ) NEW_LINE DEDENT else : NEW_LINE INDENT vp [ n ] . append ( i ) NEW_LINE vp [ n ] . append ( int ( n / i ) ) NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT DEDENT def countSeq ( N , K ) : NEW_LINE INDENT i = 0 NEW_LINE j = 0 NEW_LINE k = 0 NEW_LINE dp = [ [ 0 for i in range ( 109 ) ] for j in range ( 109 ) ] NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT finding_factors ( i ) NEW_LINE dp [ 0 ] [ i ] = 0 NEW_LINE dp [ 1 ] [ i ] = 1 NEW_LINE DEDENT for i in range ( 2 , K + 1 ) : NEW_LINE INDENT for j in range ( 1 , N + 1 ) : NEW_LINE INDENT Sum = 0 NEW_LINE for k in range ( len ( vp [ j ] ) ) : NEW_LINE INDENT Sum += dp [ i - 1 ] [ vp [ j ] [ k ] ] NEW_LINE DEDENT dp [ i ] [ j ] = Sum NEW_LINE DEDENT DEDENT ans = 0 NEW_LINE for j in range ( 1 , N + 1 ) : NEW_LINE INDENT ans += dp [ K ] [ j ] NEW_LINE DEDENT return ans NEW_LINE DEDENT N = 3 NEW_LINE K = 2 NEW_LINE print ( countSeq ( N , K ) ) NEW_LINE