Count sequences of length K having each term divisible by its preceding term | Java 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
import java . util . * ; class GFG { @ SuppressWarnings ( " unchecked " ) static Vector < Integer > [ ] vp = new Vector [ 2009 ] ; static void finding_factors ( int n ) { int i , a ; 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 ] . size ( ) ; k ++ ) { sum = ( sum + dp [ i - 1 ] [ vp [ j ] . get ( 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 Vector < Integer > ( ) ; System . out . print ( countSeq ( N , K ) + "NEW_LINE"); } }