C++で指定範囲内の非推移的な互いに素なトリプルを見つける方法

問題の概要

下限(left)と上限(right)が与えられたとき、次の条件をすべて満たす非推移的なトリプル (x, y, z) を見つけることを考えます。

• ペア (x, y) は互いに素である(最大公約数が1)
• ペア (y, z) も互いに素である
• しかし、ペア (x, z) は互いに素ではない

「互いに素」という性質は推移的ではないため、このような組み合わせが存在し得ます。例えば、下限が2、上限が10の場合、候補となる要素は {2, 3, 4, 5, 6, 7, 8, 9, 10} です。この中では (4, 7, 8) が条件を満たします。GCD(4, 7) = 1、GCD(7, 8) = 1 ですが、GCD(4, 8) = 4 となり、(4, 8) は互いに素ではないためです。

アプローチ:全探索(ブルートフォース)

ここでは最もシンプルな全探索のアプローチを採用します。指定された範囲内で作成できるすべてのトリプルを順番に生成し、それぞれが上記の条件に一致するかどうかを確認していきます。条件を満たすトリプルが最初に見つかった時点で探索を打ち切り、その結果を出力します。

実装例(C++)

#include <iostream>
#include <algorithm>
using namespace std;

// 2つの整数が互いに素かどうかを判定する関数
bool isCoprime(int a, int b) {
    return (__gcd(a, b) == 1);
}

void tripletInRange(int left, int right) {
    bool flag = false;
    int A, B, C;

    // left〜right の範囲で作れるすべてのトリプルを生成してチェック
    for (int a = left; a <= right && !flag; a++) {
        for (int b = a + 1; b <= right && !flag; b++) {
            for (int c = b + 1; c <= right; c++) {
                if (isCoprime(a, b) && isCoprime(b, c) && !isCoprime(a, c)) {
                    flag = true;
                    A = a;
                    B = b;
                    C = c;
                    break;
                }
            }
        }
    }

    if (flag) {
        cout << "(" << A << ", " << B << ", " << C << ") は "
             << left << " から " << right << " の間に存在する条件を満たすトリプルの一つです" << endl;
    } else {
        cout << left << " から " << right << " の間に条件を満たすトリプルは存在しません" << endl;
    }
}

int main() {
    int left = 2, right = 10;
    tripletInRange(left, right);
}

出力結果

(4, 5, 6) は 2 から 10 の間に存在する条件を満たすトリプルの一つです

コードの解説

isCoprime関数: 引数として受け取った2つの整数の最大公約数(GCD)を __gcd で計算し、それが1であれば true を返します。これにより、2つの値が互いに素かどうかを簡単に判定できます。

tripletInRange関数: 3重のforループを使って、範囲内のすべての組み合わせ (a, b, c)(a < b < c)を生成します。各組み合わせに対して、「(a, b) が互いに素」「(b, c) が互いに素」「(a, c) が互いに素ではない」という3つの条件を評価し、すべて満たした場合にフラグを立てて結果を記録します。外側のループにも !flag 条件を設けることで、最初のトリプルが見つかった時点で効率よく探索を終了できるようにしています。

計算量について

範囲内の要素数を n とすると、3重ループによってすべての組み合わせを調べるため、時間計算量は O(n³) となります。一方、追加のデータ構造を使用しないため、空間計算量は O(1) です。範囲が狭い場合には十分実用的ですが、範囲が広くなると処理時間が急増するため、より高度なアルゴリズムの検討が必要になります。

補足:std::gcd の利用

サンプルコードで使用している __gcd はGCC固有の拡張関数です。C++17以降の環境では、<numeric> ヘッダーに含まれる標準の std::gcd を使用することが推奨されます。移植性の高いコードを目指す場合は、isCoprime 関数内を return (std::gcd(a, b) == 1); に置き換えるだけで対応できます。