Count of arrays in which all adjacent elements are such that one of them divide the another | C ++ program to count number of arrays of size n such that every element is in range [ 1 , m ] and adjacen are divisible ; For storing factors . ; For storing multiples . ; calculating the factors and multiples of elements [ 1. . . m ] . ; Initialising for size 1 array for each i <= m . ; Calculating the number of array possible of size i and starting with j . ; For all previous possible values . Adding number of factors . ; Adding number of multiple . ; Calculating the total count of array which start from [ 1. . . m ] . ; Driven Program
#include <bits/stdc++.h> NEW_LINE #define MAX  1000 NEW_LINE using namespace std ; int numofArray ( int n , int m ) { int dp [ MAX ] [ MAX ] ; vector < int > di [ MAX ] ; vector < int > mu [ MAX ] ; memset ( dp , 0 , sizeof dp ) ; memset ( di , 0 , sizeof di ) ; memset ( mu , 0 , sizeof mu ) ; for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 2 * i ; j <= m ; j += i ) { di [ j ] . push_back ( i ) ; mu [ i ] . push_back ( j ) ; } di [ i ] . push_back ( i ) ; } for ( int i = 1 ; i <= m ; i ++ ) dp [ 1 ] [ i ] = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= m ; j ++ ) { dp [ i ] [ j ] = 0 ; for ( auto x : di [ j ] ) dp [ i ] [ j ] += dp [ i - 1 ] [ x ] ; for ( auto x : mu [ j ] ) dp [ i ] [ j ] += dp [ i - 1 ] [ x ] ; } } int ans = 0 ; for ( int i = 1 ; i <= m ; i ++ ) { ans += dp [ n ] [ i ] ; di [ i ] . clear ( ) ; mu [ i ] . clear ( ) ; } return ans ; } int main ( ) { int n = 3 , m = 3 ; cout << numofArray ( n , m ) << " STRNEWLINE " ; return 0 ; }