C++で指定した値と等しいGCD（最大公約数）を持つ自然数のペアを数える方法

この記事では、3つの入力変数「start（開始値）」「end（終了値）」「number（指定値）」が与えられたとき、startからendの範囲内にあり、かつGCD（最大公約数）が「number」と等しい数のペアを求める方法を解説します。つまり、GCD(A, B) = number を満たし、AとBがどちらも範囲 [start, end] 内に含まれるようなペア (A, B) の個数をカウントします。

具体例で確認してみましょう。

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

出力 − GCDが指定値と等しい自然数のペアの個数 − 3

説明 − 5から20の範囲でGCDが8となるペアは (8,8)、(8,16)、(16,8) の3つです。

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

出力 − GCDが指定値と等しい自然数のペアの個数 − 2

説明 − 5から20の範囲でGCDが7となるペアは (21,28)、(28,21) の2つです。

素朴なアプローチ（ナイーブ法）

まず紹介するのは最もシンプルな方法です。外側のforループを i=start から i<=end まで、内側のforループを j=start から j<=end まで回し、各ペア (i, j) について GCD(i, j) == number が成り立つかどうかを判定します。条件を満たしていればカウントを1増やします。

• 変数 start、end、number を整数として受け取ります。
• 関数 GCD(int a, int b) は再帰的に呼び出され、引数 a と b の最大公約数を返します。
• b が0でなければ GCD(b, a % b) として自分自身を再帰呼び出しし、b が0なら a を返します。
• 関数 GCD_pairs(int start, int end, int number) は境界値 start・end と指定値 number を受け取り、GCDが number と等しいペアの個数を返します。
• カウントの初期値を0に設定します。
• ペアの各要素に対して二重のforループを使用します。外側のループは i=start から i<=end まで、内側のループは j=start から j<=end まで繰り返します。
• ペア (i, j) について GCD(i, j) == number が成立するかをチェックし、真であればカウントを増やします。
• 最終的に、GCDが number と等しいペアの総数が得られます。
• そのカウントを結果として返します。

効率的なアプローチ

次に、計算量を大幅に削減できる効率的な方法を紹介します。ペア (i, j) のGCDが number になるためには、i と j の両方が number で割り切れる必要があります。start から end の間で number で割り切れる数は最大でも (end - start) / number 個程度しか存在しないため、探索範囲を絞り込むことができます。具体的には、start = (start + number - 1) / number から end = end / number までの範囲にスケールダウンして走査します。そして、その範囲内の各数について GCD(i, j) == 1 が成り立てば、元のペアのGCDは number になるため、カウントを増やします。

• 変数 start、end、number を整数として受け取ります。
• start = (start + number - 1) / number、end = end / number として更新します。
• 関数 GCD(int a, int b) は再帰的に呼び出され、引数 a と b の最大公約数を返します。
• b が0でなければ GCD(b, a % b) として自分自身を再帰呼び出しし、b が0なら a を返します。
• 関数 GCD_pairs(int start, int end, int number) は境界値 start・end と指定値 number を受け取り、該当するペアの個数を返します。
• カウントの初期値を0に設定します。
• 二重のforループでペアの各要素を走査します。外側のループは i=start から i<=end まで、内側のループは j=start から j<=end まで繰り返します。
• ペア (i, j) について GCD(i, j) == 1 が成立するかをチェックし、真であればカウントを増やします。
• 最終的に、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