C++でGCD1を使用したサブシーケンスの数をカウントします

整数要素の配列が与えられ、タスクは、GCDが1である与えられた配列からサブシーケンスを見つけることです。GCDは2つ以上の最大公約数です。与えられた数を完全に、そしてすべての中で最大に分割する整数。

入力 − int arr [] ={3、4、8、16}

出力 − GCD 1のサブシーケンスの数は− 7

説明 −

GCDを1として指定されたアレイから形成できるサブシーケンスは、（3、4）、（3、8）、（3、16）、（4、3）、（8、3）、（16、 3）、（3、4、8）

入力 − int arr [] ={5、7、10}

出力 − GCD 1のサブシーケンスの数は− 3

説明 −

GCDを1として指定されたアレイから形成できるサブシーケンスは、（5、7）、（7、10）、（5、7、10）

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

• 任意のサイズの整数要素の配列を入力します。

• 配列のサイズを計算し、さらに処理するためにデータを関数に渡します

• 一時変数カウントを宣言して、GCDのサブシーケンスのカウントを1として格納します

• 配列のサイズまでiから0までのループFORを開始します

• ループ内で、配列のサイズになるまでjから0までの別のループFORを開始します

• ループ内で、IF GCD（arr [i]、arr [j]）=TRUEを確認してから、カウントを1ずつ増やします

• 返品数

• 結果を印刷します。

例

# include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
   if (a == 0)
      return b;
   return gcd(b % a, a);
}
int GCD_1(int arr[],int size){
   int count = 0;
   for(int i=0;i<size;i++){
      for(int j=0;j<=size;j++){
         if(gcd(arr[i],arr[j])==1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = {3, 4, 8, 16};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of number of sub-sequences with GCD 1 are: "<<GCD_1(arr, size);
   return 0;
}

出力

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

Count of number of sub-sequences with GCD 1 are: 7