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 Math . sqrt ( N ) ; Function to return the count of sequences of length K having alet 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 alet dp [ i - 1 ] [ vp [ j ] [ k ] ] ; vp [ j ] [ k ] stores alet factors of j ; Store the sum in A [ i ] [ j ] ; Sum of alet dp [ K ] [ j ] obtain all K length sequences ending with j ; Driver Code
let vp = new Array ( 2009 ) ; function finding_factors ( n ) { let i , a ; for ( i = 1 ; i * i <= n ; i ++ ) { if ( n % i == 0 ) { if ( i * i == n ) { vp [ n ] . push ( i ) ; } else { vp [ n ] . push ( i ) ; vp [ n ] . push ( n / i ) ; } } } } function countSeq ( N , K ) { let i , j , k ; let dp = new Array ( 109 ) ; for ( let i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( 2 ) ; } for ( i = 1 ; i <= N ; i ++ ) { finding_factors ( i ) ; dp [ 0 ] [ i ] = 0 ; dp [ 1 ] [ i ] = 1 ; } for ( i = 2 ; i <= K ; i ++ ) { for ( j = 1 ; j <= N ; j ++ ) { let sum = 0 ; for ( k = 0 ; k < vp [ j ] . length ; k ++ ) { sum = ( sum + dp [ i - 1 ] [ vp [ j ] [ k ] ] ) ; } dp [ i ] [ j ] = sum ; } } let ans = 0 ; for ( j = 1 ; j <= N ; j ++ ) { ans = ( ans + dp [ K ] [ j ] ) ; } return ans ; } let N , K ; N = 3 ; K = 2 ; for ( let i = 0 ; i < vp . length ; i ++ ) vp [ i ] = [ ] ; document . write ( countSeq ( N , K ) + " " ) ;