C ++でgcd（A、B）がBになるように、ペア（A <=N、B <=N）の数を数えます

入力Nが与えられます。目標は、1 <=A<=Nおよび1<=B <=Nであり、GCD（A、B）がBであるようなA、Bのすべてのペアを見つけることです。 Bとしての最大公約数。

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

入力 − n =5

出力 − gcd（A、B）がBになるようにペア（A <=N、B <=N）の数を数える-10

説明

pairs (A <= N, B <= N) such that gcd (A , B) is B are −
(1,1), (2,1),(3,1),(4,1),(5,1),(2,2),(3,3),(4,2),(4,4), (5,5). Total 10.

入力 − n =50

出力 − gcd（A、B）がBになるようなペア（A <=N、B <=N）の数を数える− 207

説明

pairs (A <= N, B <= N) such that gcd (A , B) is B are :
(1,1), (2,1),(3,1),(4,1),(5,1).....(50,1)
(2,2),(3,3),(4,4).....(50,50)

同様に、（4,2）、（6,3）、（8,2）、（8,4）、...........（50,25）のような他のペア。合計207

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

与えられた問題を解決するための複数のアプローチ、すなわちナイーブなアプローチと効率的なアプローチがあります。それでは、最初にナイーブなアプローチを見てみましょう。 。

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

• 関数GCD（int A、int B）は、2つの整数を取り、AとBの最大公約数を返します。gcdを再帰的に計算します。

• AまたはBのいずれかが0の場合、別のものを返します。両方が等しい場合は、2つの値のいずれかを返します。 A> Bの場合は（A-B、B）を返します。 Bが大きい場合は、gcd（B-A、A）を返します。最終的に、gcd値を取得します。

• 関数count_pairs（int N）はNを取り、pair（A、B）でBがgcdであり、両方がrange [1、N]にあるようなペアの数を返します。

• そのようなペアの数のカウント=0として初期値を取ります。

• ペアの値ごとに、forループi=1からi=N（Aの場合）を実行し、ネストされたforループj =1 t j =N（Bの場合）を実行します。

• ペア（i、j）を作成し、GCD（i、j）に渡します。結果がjに等しい場合。インクリメントカウント。

• 両方のループの終わりに、結果としてカウントを返します。

効率的なアプローチ

ご覧のとおり、gcd（a、b）=bは、aが常にbの倍数であることを意味します。 N未満のb（1 <=b <=N）のそのような倍数はすべて、ペアになります。数iの場合、iの倍数がfloor（N / i）未満の場合、カウントされます。

• 関数count_pairs（int N）はNを取り、pair（A、B）でBがgcdであり、両方がrange [1、N]にあるようなペアの数を返します。

• そのようなペアの数のカウント=0として初期値を取ります。

• 一時変数temp=Nおよびi=1を取ります。

• while（i <=N）を使用してフォローする

• それぞれについて、倍数の限界をj =N / temp

  として計算します。

• 現在のiのペアの数はtemp*（i-j + 1）になります。カウントに追加します。

• i =j+1に設定します。 （A、B）の次のBについて。

• 次の反復のためにtemp=N/iを設定します。

• whileループの最後に、結果としてカウントを返します。

例（素朴なアプローチ）

#include <iostream>
using namespace std;
int GCD(int A, int B){
   if (A == 0){
      return B;
   }
   if (B == 0){
      return A;
   }
   if (A == B){
      return A;
   }
   if (A > B){
      return GCD(A-B, B);
   }
   return GCD(A, B-A);
}
int count_pairs(int N){
   int count = 0;
   for(int i=1; i<=N; i++){
      for(int j = 1; j<=N; j++){
         if(GCD(i, j)==j){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int N = 4;
   cout<<"Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: "<<count_pairs(N);
   return 0;
}

出力

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

Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8

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

#include <bits/stdc++.h>
using namespace std;
int Count_pairs(int N){
   int count = 0;
   int temp = N;
   int i = 1;
   while(i <= N){
      int j = N / temp;
      count += temp * (j - i + 1);
      i = j + 1;
      temp = N / i;
   }
   return count;
}
int main(){
   int N = 4;
   cout<<"Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: "<<Count_pairs(N);
   return 0;
}

出力

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

Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B are: 8