隣接するすべての要素が、C++で一方が他方を分割するような配列の数

「one」と「another」という名前の2つの整数が与えられます。目標は、-

• 配列内の要素は、1から「別の」までの範囲にあります。

• 配列のすべての要素は、arr[i]がarr[i+1]を分割するかarr[i+1]がarr[i+2]....を分割するようなものです。

• 配列の長さは「1」です。

例

入力

one = 3, another = 2

出力

Count of arrays in which all adjacent elements are such that one of them divide the another are: 8

説明

The arrays will be:
[ 1,1,1 ], [ 1,1,2 ], [ 1,2,1 ], [ 1,2,2 ], [ 2,1,1 ], [ 2,1,2 ], [ 2,2,1 ], [ 2,2,2 ]

入力

one = 2, another = 3

出力

Count of arrays in which all adjacent elements are such that one of them divide the another are: 7

説明

The arrays will be:
[ 1,1 ], [ 2,2 ], [ 3,3 ], [ 1,2 ], [ 1,3 ], [ 2,2 ], [ 3,3 ]

以下のプログラムで使用されるアプローチは次のとおりです −

各配列の最初の要素は、[1、another]の範囲内の任意の数にすることができます。次の要素は、除算条件が成立するように、常に前の倍数または前の因数になります。また、係数または倍数は「別の」よりも小さくする必要があります。動的計画法を使用して計算を保存します。このために、配列arr[][]。arr[1][another]を使用します。これは、単一要素の配列であるためです。 arr [i] [j] =arr [i-1] [j] +前の要素の因数+前の要素の倍数（別の要素よりも小さい）

• 入力として整数を取ります。

• 関数隣接要素（int first、int second）は、隣接するすべての要素が、一方が他方を分割するような配列の数を返します。

• 初期カウントを0とし、配列arr[size][size]。

• memsetを使用してすべてのカウントを0として初期化します。

• 2つのベクトルを取ります-因子を格納するためのvecと倍数を格納するためのvec_2。

• i=tからi=secondおよびj=2*iからj=secondへの2つのforループを使用してトラバースします。 jをiでインクリメントします。

• iをvec[j]に追加し、jをvec_2[i]に追加します。 jループの後、vec[i]にもiを追加します。

• forループを使用してarr[1][i]を設定します。

• 配列をもう一度トラバースし、vecとvec_2をトラバースして、因子と倍数をarr[i][j]に追加します。

• 最後に、すべてのarr [first] [i]を追加して、vec[i]とvec_2[i]をカウントしてクリアします。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
#define size 1000
int adjacent_elements(int first, int second){
   int count = 0;
   int arr[size][size];
   memset(arr, 0, sizeof arr);
   vector<int> vec[size], vec_2[size];
   memset(vec, 0, sizeof vec);
   memset(vec_2, 0, sizeof vec_2);
   for (int i = 1; i <= second; i++){
      for (int j = 2*i; j <= second; j += i){
         vec[j].push_back(i);
         vec_2[i].push_back(j);
      }
      vec[i].push_back(i);
   }
   for (int i = 1; i <= second; i++){
      arr[1][i] = 1;
   }
   for (int i = 2; i <= first; i++){
      for (int j = 1; j <= second; j++){
         arr[i][j] = 0;
         for (auto it: vec[j]){
            arr[i][j] += arr[i−1][it];
         }
         for (auto it : vec_2[j]){
            arr[i][j] += arr[i−1][it];
         }
      }
   }
   for (int i = 1; i <= second; i++){
      count = count + arr[first][i];
      vec[i].clear();
      vec_2[i].clear();
   }
   return count;
}
int main(){
   int one = 2, another = 2;
   cout<<"Count of arrays in which all adjacent elements are such that one of them divide the another are: "<<adjacent_elements(one, another);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of arrays in which all adjacent elements are such that one of them divide the another are: 4