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

説明：

(1,1), (2,1), (3,1), (4,1), (5,1),
(2,2), (3,3), (4,2), (4,4), (5,5) の合計 10 個

入力： N = 50

出力： gcd(A, B) が B となるペア (A ≤ N, B ≤ N) の個数 ― 207

説明：

(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 の最大公約数を返します。再帰的に計算を行います。
• A または B のどちらかが 0 なら、もう一方を返します。両者が等しければ、いずれかの値を返します。A > B であれば GCD(A−B, B) を、B の方が大きければ GCD(A, B−A) を返します。これを繰り返すことで gcd の値が得られます。
• 関数 count_pairs(int N) は N を受け取り、ペア (A, B) において B が gcd と一致し、両方が [1, N] の範囲に収まるようなペアの個数を返します。
• ペアの個数を数えるため、初期値 count = 0 を用意します。
• 各ペアの値について、A に対応する for ループ（i = 1 から i = N まで）と、B に対応する入れ子の for ループ（j = 1 から j = N まで）を実行します。
• ペア (i, j) を作成して GCD(i, j) に渡し、結果が j と一致したら count をインクリメントします。
• 両方のループが終了した時点で、count を結果として返します。

効率的なアプローチ

GCD(a, b) = b が成り立つということは、a が必ず b の倍数であることを意味します。したがって、N 以下の b（1 ≤ b ≤ N）の倍数はすべて条件を満たすペアを作ります。ある数 i については、N 以下の i の倍数の個数、すなわち floor(N / i) 個がカウント対象になります。

• 関数 Count_pairs(int N) は N を受け取り、条件を満たすペアの個数を返します。
• 初期値として count = 0 を用意します。
• 一時変数 temp = N、i = 1 とします。
• while (i ≤ N) のループ内で以下の処理を行います。
• 各 i について、商の値が同じ区間の末尾 j = N / temp を求めます。
• 現在の区間に含まれるペアの数は temp × (j − i + 1) なので、これを count に加算します。
• i = j + 1 とし、次の B の候補へ進みます。
• 次回の反復に備えて temp = N / i を更新します。
• while ループが終了したら、count を結果として返します。

実装例（ナイーブなアプローチ）

#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<<"gcd(A, B) が B となるペア (A <= N, B <= N) の個数: "<<count_pairs(N);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

gcd(A, B) が B となるペア (A <= N, B <= N) の個数: 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<<"gcd(A, B) が B となるペア (A <= N, B <= N) の個数: "<<Count_pairs(N);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

gcd(A, B) が B となるペア (A <= N, B <= N) の個数: 8