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 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE vector < ll int > vp [ 2009 ] ; void finding_factors ( ll int n ) { ll int i , a ; for ( i = 1 ; i * i <= n ; i ++ ) { if ( n % i == 0 ) { if ( i * i == n ) { vp [ n ] . push_back ( i ) ; } else { vp [ n ] . push_back ( i ) ; vp [ n ] . push_back ( n / i ) ; } } } } ll int countSeq ( ll int N , ll int K ) { ll int i , j , k ; ll int dp [ 109 ] [ 109 ] = { 0 } ; 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 ++ ) { ll int sum = 0 ; for ( k = 0 ; k < vp [ j ] . size ( ) ; k ++ ) { sum = ( sum + dp [ i - 1 ] [ vp [ j ] [ k ] ] ) ; } dp [ i ] [ j ] = sum ; } } ll int ans = 0 ; for ( j = 1 ; j <= N ; j ++ ) { ans = ( ans + dp [ K ] [ j ] ) ; } return ans ; } int main ( ) { ll int N , K ; N = 3 ; K = 2 ; cout << countSeq ( N , K ) << endl ; return 0 ; }