C++でGCDが1となる部分列の個数を数える方法

整数型の要素からなる配列が与えられ、その中から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) の7つです。

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

出力 − GCDが1となる部分列の個数 − 3

説明 −
与えられた配列から作成できる、GCDが1となる部分列は (5, 7)、(7, 10)、(5, 7, 10) の3つです。

プログラムで使用しているアプローチ

• 任意のサイズの整数型配列を入力として受け取ります。

• 配列のサイズを計算し、以降の処理のためにデータを関数へ渡します。

• GCDが1となる部分列の個数を格納するための一時変数 count を宣言します。

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

• そのループの中で、j を 0 から配列のサイズまで動かす別の FOR ループを開始します。

• ループ内で IF 文により GCD(arr[i], arr[j]) == 1 であるかどうかを判定し、真であれば count を 1 増やします。

• count を返します。

• 結果を出力します。

サンプルコード

このコードでは、ユークリッドの互除法を再帰的に利用して2つの整数の最大公約数を求める gcd 関数を定義しています。そして GCD_1 関数の中で二重ループによって配列内の要素同士の組み合わせをすべて調べ、GCDが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