配列のGCDをkの倍数にするための最小操作回数をC++で求める方法

問題の概要

配列 arr と整数 k が与えられたとき、配列全体の GCD(最大公約数)を k の倍数に一致させるために必要な最小の操作回数を求めます。ここでいう「操作」とは、任意の要素の値を 1 増やす、または 1 減らすことを指します。

例として、配列が {4, 5, 6}、k = 5 の場合を考えてみます。4 を 1 増やして 5 にし、6 を 1 減らして 5 にすれば、すべての要素が 5 の倍数になり、GCD も 5 となります。このとき必要な操作回数は 2 回です。

アルゴリズムの手順

配列の GCD を k の倍数にするには、すべての要素を k の倍数に揃える必要があります。以下の手順に従うことで答えを求められます。

• 配列内のすべての要素 e に対して、手順2と3を実行する
• e が 1 ではなく、かつ e > k の場合:result に min(e mod k, k − e mod k) を加算する(余りをもとに、切り上げと切り下げの近い方を選択)
• それ以外の場合:result に k − e を加算する(要素を k まで引き上げる)
• 最終的な result を返す

C++による実装例

#include <iostream>
using namespace std;
int countMinOp(int arr[], int n, int k) {
    int result = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] != 1 && arr[i] > k) {
            result = result + min(arr[i] % k, k - arr[i] % k);
        } else {
            result = result + k - arr[i];
        }
    }
    return result;
}
int main() {
    int arr[] = { 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 5;
    cout << "Minimum operation required: " << countMinOp(arr, n, k);
}

出力

Minimum operation required: 2

処理のポイント

このアルゴリズムでは、各要素ごとに「最も近い k の倍数」までの距離を計算しています。要素が k より大きい場合は、剰余 (e mod k) を利用することで、切り上げた場合と切り下げた場合のどちらが近いかを 1 回の計算で判定できます。一方、要素が k 以下の場合は k まで引き上げるほかに選択肢がないため、単純に差分を加算します。

全体の計算量は O(n) であり、要素数が多い配列でも高速に動作するのが特徴です。貪欲法的なアプローチにより、各要素の最小操作の総和がそのまま答えになる点も理解しておきましょう。