C++で各配列要素の剰余がすべて等しくなる数「k」を見つける方法

このチュートリアルでは、配列の各要素で割った余り(剰余)がすべて等しくなるような数kを見つけるプログラムを作成します。まずは具体例から見ていきましょう。

入力: arr = {10, 4, 2}

出力: 1 2

解法の鍵となる剰余の性質

2つの数 x と y(x > y)を考え、その差を x - y = d とします。このとき x = y + d と表せます。

ここで、x % k = y % k を満たす数 k が存在すると仮定し、この関係式に k を法とする剰余演算を適用すると、d に関する重要な性質が導かれます。

x % k = (y + d) % k
(y + d) % k = (y % k + d % k) % k
→ d % k = 0

この計算結果から、k が x と y の差 d の約数であれば、x と y を k で割った余りが一致する候補になり得ることが分かります。

この性質を配列の要素全体に適用して k を求めていきます。問題を解く手順は以下の通りです。

• 配列を数値で初期化します。
• 配列をソートし、最大値と最小値の差を d とします。
• d が 0 の場合、すべての要素が同一であることを意味します。この場合、どんな数で割っても剰余は必然的に等しくなるため、k は無数に存在します。
• d が 0 でない場合は、d の約数をすべて列挙して候補として保存します。
• 各約数について、配列の全要素との剰余が一致するかどうかを検証し、条件を満たすものを出力します。

C++での実装例

それでは、上記の手順を実装したコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

// 全要素に対する剰余が等しくなるkを見つける関数
void findNumbers(int arr[], int n) {
    // 配列を昇順にソート
    sort(arr, arr + n);
    int d = arr[n - 1] - arr[0];

    // すべての要素が同一かどうかを判定
    if (d == 0) {
        cout << "Infinite number of k's";
        return;
    }

    // dの約数をすべて求める
    vector<int> v;
    for (int i = 1; i * i <= d; i++) {
        if (d % i == 0) {
            v.push_back(i);
            if (i != d / i) {
                v.push_back(d / i);
            }
        }
    }

    // 条件を満たすkを出力
    for (int i = 0; i < v.size(); i++) {
        int temp = arr[0] % v[i];
        int j;
        for (j = 1; j < n; j++) {
            if (arr[j] % v[i] != temp) {
                break;
            }
        }
        if (j == n)
            cout << v[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {10, 4, 2};
    findNumbers(arr, 3);
    return 0;
}

実行結果

上記のコードをコンパイルして実行すると、次のような出力が得られます。

1 2

配列 {10, 4, 2} の最大値と最小値の差は 8 であり、その約数は 1, 2, 4, 8 です。この中で全要素との剰余が一致するのは 1 と 2 だけであるため、これらが出力されます。

計算量について

d の約数の列挙には O(√d) の計算時間がかかり、各候補の検証には配列の長さ n に比例した時間が必要です。そのため全体の計算量は O(√d + n × τ(d))(τ(d) は d の約数の個数)となり、非常に効率的なアルゴリズムと言えます。

まとめ

本チュートリアルでは、「k は必ず最大値と最小値の差の約数になる」という剰余の性質を利用して、配列の全要素に対する剰余が等しくなる数を効率よく見つける方法を解説しました。本記事についてご不明な点がありましたら、コメント欄でお気軽にお知らせください。