C++で約数のリストから2つの数AとBを求める方法

このチュートリアルでは、次の問題の解き方を詳しく解説します。

問題の概要

整数の配列が与えられたとき、そこから2つの数 A と B を見つける必要があります。配列に含まれる残りの数は、すべて A または B の約数です。

また、ある数が A と B の両方の約数である場合、その数は配列の中に2回出現します。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• 配列内の最大値は、A と B のどちらか一方に必ず該当します。ここでは、それを A とします。
• 次に、B は「2番目に大きい数」、または「A の約数ではない数」のいずれかになります。

考え方のポイント

配列を降順に走査しながら、A を割り切れない最初の数、もしくは連続して重複している数（同じ約数が2回現れるケース）を見つければ、それが B であると判断できます。

実装例（C++コード）

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void findTheDivisors(int arr[], int n) {
   sort(arr, arr + n);
   int A = arr[n - 1], B = -1;
   for (int i = n - 2; i > -1; i--) {
      if (A % arr[i] != 0) {
         B = arr[i];
         break;
      }
      if (i - 1 >= 0 && arr[i] == arr[i - 1]) {
         B = arr[i];
         break;
      }
   }
   cout << "A = " << A << ", B = " << B << endl;
}
int main() {
   int arr[] = { 3, 2, 3, 4, 12, 6, 1, 1, 2, 6 };
   findTheDivisors(arr, 10);
   return 0;
}

コードの解説

1. まず、配列を昇順にソートします。
2. 最大値を A として取得し、B を初期値 -1 で設定します。
3. 後ろから順に各要素をチェックし、A で割り切れない数が見つかれば、それを B として出力します。
4. また、直前の要素と同じ値（重複した約数）が見つかった場合も、それを B とします。

実行結果

上記のプログラムを実行すると、次の出力が得られます。

A = 12, B = 6

この例では、配列内の最大値 12 が A となり、A の約数ではない 6 が B として正しく検出されています。

まとめ

このチュートリアルでは、約数のリストから元となる2つの数 A と B を求めるアルゴリズムを学びました。ソートと線形探索を組み合わせることで、シンプルかつ効率的に解ける問題です。本記事についてご不明な点がある場合は、コメント欄でお気軽にお尋ねください。