Count sequences of length K having each term divisible by its preceding term | C # program to implement the above approach ; 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 aint 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 aint dp [ i - 1 , vp [ j , k ] ] ; vp [ j , k ] stores aint factors of j ; Store the sum in A [ i , j ] ; Sum of aint dp [ K , j ] obtain all K length sequences ending with j ; Driver code
using System ; using System . Collections . Generic ; class GFG { static List < int > [ ] vp = new List < int > [ 2009 ] ; static void finding_factors ( int n ) { int i ; for ( i = 1 ; i * i <= n ; i ++ ) { if ( n % i == 0 ) { if ( i * i == n ) { vp [ n ] . Add ( i ) ; } else { vp [ n ] . Add ( i ) ; vp [ n ] . Add ( n / i ) ; } } } } static int countSeq ( int N , int K ) { int i , j , k ; int [ , ] dp = new int [ 109 , 109 ] ; 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 ++ ) { int sum = 0 ; for ( k = 0 ; k < vp [ j ] . Count ; k ++ ) { sum = ( sum + dp [ i - 1 , vp [ j ] [ k ] ] ) ; } dp [ i , j ] = sum ; } } int ans = 0 ; for ( j = 1 ; j <= N ; j ++ ) { ans = ( ans + dp [ K , j ] ) ; } return ans ; } public static void Main ( String [ ] args ) { int N , K ; N = 3 ; K = 2 ; for ( int i = 0 ; i < vp . Length ; i ++ ) vp [ i ] = new List < int > ( ) ; Console . Write ( countSeq ( N , K ) + " STRNEWLINE " ) ; } }