【C++】arr[i] ≥ arr[j] を満たす配列の全ペアにおける最大剰余の求め方

問題概要

この問題では、n 個の要素からなる配列が与えられます。求めるのは、arr[i] ≥ arr[j] を満たすすべてのペアの中で最大の剰余（modulo）の値です。

つまり、arr[i] ≥ arr[j] という条件のもとで、arr[i] % arr[j] の最大値を見つけることが目的となります。

問題を理解するための例

入力： arr[] = {3, 5, 9}

出力： 4

説明：

考えられるすべてのペア arr[i] と arr[j]:
5, 3 => 5%3 = 2
9, 3 => 9%3 = 0
9, 5 => 9%5 = 4

この中で最も大きい剰余は 4 となるため、答えは 4 になります。

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

最もシンプルな方法は、二重ループを回してすべてのペアについて剰余を計算し、その最大値を求めることです。しかしこの方法の計算量は O(n²) となるため、要素数が多い配列に対しては非効率です。

効率的な解法

より効率的なアプローチは、ソート済みの配列に対して適用します。アルゴリズムは次の手順で動作します。

• 配列内の各要素 arr[j] について、arr[j] の倍数 x を、配列の最大要素を超えるまで順に生成していきます。
• x 未満となる最大の配列要素（arr[i] < x を満たす要素）を見つけます。
• arr[i] % arr[j] を計算し、処理のたびにその最大値を変数 maxModulo に保存・更新します。

アルゴリズムの動作例

arr = {3, 5, 9}
arr[j] = 3 の場合（j = 0）,
x = {6, 9}
x = 6 のとき、arr[i] = 5,
arr[i]%arr[j] = 5%3 = 2, maxModulo = 2
x = 9 のとき、arr[i] = 9,
arr[i]%arr[j] = 9%3 = 0, maxModulo = 2
arr[j] = 5 の場合（j = 1）,
x = {10}
x = 10 のとき、arr[i] = 9,
arr[i]%arr[j] = 9%5 = 4, maxModulo = 4

C++ 実装例

arr[i] ≥ arr[j] を満たす配列の全ペアの最大剰余を求めるプログラム：

#include <bits/stdc++.h>
using namespace std;
int maxModulo(int arr[], int n) {
    int maxModulo = 0;
    sort(arr, arr + n);
    for (int j = n - 2; j >= 0; --j) {
        if (maxModulo >= arr[j])
            break;
        if (arr[j] == arr[j + 1])
            continue;
        for (int k = 2 * arr[j]; k <= arr[n - 1] + arr[j]; k += arr[j]) {
            int i = lower_bound(arr, arr + n, k) - arr;
            maxModulo = max(maxModulo, arr[i - 1] % arr[j]);
        }
    }
    return maxModulo;
}
int main() {
    int arr[] = {3, 5, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum modulo of all pairs is "<<maxModulo(arr, n);
}

出力

The maximum modulo of all pairs is 4

まとめ

このアルゴリズムは、配列をあらかじめソートしておき、各除数 arr[j] の倍数を基準に二分探索（lower_bound）を活用することで、全ペアを総当たりする O(n²) の手法よりも高速に最大剰余を求められます。さらに、現在の maxModulo が arr[j] 以上になった時点で探索を打ち切る枝刈りや、重複する要素のスキップによって、実行時間を大幅に短縮できる点がポイントです。