【C++】配列の全要素で剰余が等しくなる整数「k」を求めるプログラム

本記事では、与えられた配列のすべての要素に対する剰余（mod）が同じ値になるような整数「k」を見つけるC++プログラムについて解説します。

問題の概要

例として、次のような配列が与えられたとします。

arr = {12, 22, 32}

この場合、条件を満たすkの値は 1、2、5、10 となります。実際に確認してみると、これらの値で各要素を割った余りはすべて等しくなっています。

解法の考え方

まず、配列内の2つの値「x」と「y」（x > y）に注目します。両者の差を「difference」とすると、次の関係が成り立ちます。

(y + difference) % k = y % k

この式を変形すると、以下が導かれます。

difference % k = 0

つまり、「k」は配列内の最大値と最小値の差の約数でなければならないことが分かります。

そこで、以下の手順で解を求めます。

1. 配列をソートし、最大値と最小値の差（difference）を求める。
2. difference のすべての約数を列挙する。
3. 各約数について、配列の全要素の剰余が一致するかどうかを検証する。
4. 一致した約数が候補となる「k」の値である。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
int equal_modulus (int arr[], int len) {
   sort(arr, arr + len);
   int diff = arr[len-1] - arr[0];
   // 差のすべての約数を格納するvector
   vector <int> divi;
   for (int i = 1; i*i <= diff; i++) {
      if (diff%i == 0) {
         divi.push_back(i);
         if (i != diff/i)
            divi.push_back(diff/i);
      }
   }
   // 全要素で剰余が一致するかをチェック
   for (int i = 0; i < divi.size(); i++) {
      int temp = arr[0]%divi[i];
      int j;
      for (j = 1; j < len; j++)
         if (arr[j] % divi[i] != temp)
            break;
      // 条件を満たすkの値を出力
      if (j == len)
         cout << divi[i] <<" ";
   }
   return 0;
}
int main() {
   int arr[] = {12, 22, 32};
   int len = sizeof(arr)/sizeof(arr[0]);
   cout << "The values of K :" << endl;
   equal_modulus(arr, len);
   return 0;
}

実行結果

The values of K :
1 2 10 5

計算量について

約数の列挙は √difference まで試し割りを行うため O(√D)、その後の検証は約数の個数を d とすると O(d × n) となります。全体としては非常に効率的なアルゴリズムです。なお、配列の要素がすべて同じ値の場合、差が0になるため注意が必要です（この場合は任意のkが条件を満たします）。