C++で指定された数に等しいGCDを持つ自然数のペアを数えます

「start」、「end」、「number」の3つの入力変数を指定しました。目標は、GCD値が「数値」に等しい開始と終了の間の数値のペアを見つけることです。たとえば、GCD（A、B）=numberであり、A、Bの両方が[start、end]の範囲内にあります。

例を挙げて理解しましょう。

入力 − start =5 end =20 number =8

出力 −与えられた数に等しいGCDを持つ自然数のペアの数は− 3

説明 − GCDが8になるような5から20のペアは、−（8,8）、（8,16）、（16,8）

入力 − start =5 end =20 number =7

出力 −与えられた数に等しいGCDを持つ自然数のペアの数は− 2

説明 − GCDが7になるような20〜30のペアは−（21,28）、（28,21）

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

2つのアプローチを使用します。 i=startからi<=endまでのforループと、j=startからj<=endまでの内部ループを使用してトラバースする最初の単純なアプローチ。各pair（i、j）について、GCD（i、j）==numberかどうかを確認します。真のインクリメントカウントの場合。

• 変数start、end、numberを整数とします。

• 関数GCD（int a、int b）は再帰的であり、渡された引数a、bのGCDを返します。

• bがゼロ以外の場合は、GCD（b、a％b）として再帰的に呼び出し、それ以外の場合はaを返します。

• 関数GCD_pairs（int start、int end、int number）は、境界変数start、end、およびvariable numberを受け取り、gcd=numberを持つstartとendの間のペアを返します。

• 初期カウントを0とします。

• ペアのメンバーごとに2つのforループを使用します。 i=startからi<=endまでの外側のループと、j=startからj<=endまでの内側のループ。

• ペア（i、j）、GCD（i、j）==数値かどうかを確認します。 trueの場合、カウントをインクリメントします。

• 最後に、gcd=numberのペアの総数を取得します。

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

効率的なアプローチ

このアプローチでは、startとendの値を更新します。 pair（i、j）がgcd =numberを持つためには、両方のi、jが‘numberで割り切れる必要があります。 「番号」を完全に分割する最大（終了-開始）/番号番号があります。 「数値」で割り切れる開始と終了の間の数値を取得するには、開始=（開始+数値-1）/数値から終了=終了/数値までトラバースします。したがって、gcd（i、j）==1の場合、そのような数値ごとに、そのようなペア（i、j）のカウントをインクリメントします。

• 変数start、end、numberを整数とします。

• 更新開始=（開始+番号-1）/番号。そしてend=end/number。

• 関数GCD（int a、int b）は再帰的であり、渡された引数a、bのGCDを返します。

• bがゼロ以外の場合は、GCD（b、a％b）として再帰的に呼び出し、それ以外の場合はaを返します。

• 関数GCD_pairs（int start、int end、int number）は、境界変数start、end、およびvariable numberを受け取り、gcd=numberを持つstartとendの間のペアを返します。

• 初期カウントを0とします。

• ペアのメンバーごとに2つのforループを使用します。 i=startからi<=endまでの外側のループと、j=startからj<=endまでの内側のループ。

• ペア（i、j）、GCD（i、j）==1かどうかを確認します。 trueの場合、カウントをインクリメントします。

• 最後に、gcd=numberのペアの総数を取得します。

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

例（素朴なアプローチ）

#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
   return b ? GCD(b, a % b) : a; }
int GCD_pairs(int start, int end, int number){
   int count = 0;
   for (int i = start; i <= end; i++){
      for (int j = start; j <= end; j++){
         if (GCD(i, j) == number){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int start = 10, end = 30, number = 10;
   cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
   return 0;
}

出力

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

Count of pairs of natural numbers with GCD equal to given number are: 7

例（効率的なアプローチ）

#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b){
   return b ? GCD(b, a % b) : a;
}
int GCD_pairs(int start, int end, int number){
   int count = 0;
   for (int i = start; i <= end; i++){
      for (int j = start; j <= end; j++){
         if (GCD(i, j) == 1){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int start = 10, end = 30, number = 10;
   start = (start + number - 1) / number;
   end = end / number;
   cout<<"Count of pairs of natural numbers with GCD equal to given number are: "<<GCD_pairs(start, end, number) << endl;
return 0;
}

出力

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

Count of pairs of natural numbers with GCD equal to given number are: 7