C++でCの倍数かつ範囲[A, B]に含まれない最小の正の整数を求める方法

問題の概要

3つの整数 A、B、C が与えられたとき、次の条件を両方満たす最小の整数 X を求めます。

• X は C で割り切れる(X mod C = 0)
• X は範囲 [A, B] に含まれない

例として、A = 5、B = 10、C = 4 の場合を考えてみましょう。このとき答えは X = 4 となります。4 は 4 で割り切れ、かつ範囲 [5, 10] の外側にあるためです。

解法のアプローチ

この問題は定数時間 O(1) で解くことができます。考え方の手順は以下の通りです。

• ステップ1: C が範囲 [A, B] に含まれていない場合(C < A または C > B)、C 自身が条件を満たすので、そのまま C を返します。
• ステップ2: C が範囲内にある場合は、B より大きい最初の C の倍数を計算して返します。具体的には「((B ÷ C) × C) + C」という式を使います。整数除算により B 以下で最大の C の倍数を求め、それに C を加えることで、B を超える次の倍数が得られます。

サンプルコード

#include <iostream>
using namespace std;

int findMinNumber(int a, int b, int c) {
    // C が範囲 [a, b] 外なら C をそのまま返す
    if (c < a || c > b)
        return c;
    // B より大きい最初の C の倍数を求める
    int res = ((b / c) * c) + c;
    return res;
}

int main() {
    int a = 2, b = 4, c = 2;
    cout << "Minimum number X: " << findMinNumber(a, b, c);
}

実行結果

Minimum number X: 6

コードの解説

上記の例では A = 2、B = 4、C = 2 となっています。C = 2 は範囲 [2, 4] 内に存在するため、B より大きい最初の 2 の倍数を求めます。「((4 ÷ 2) × 2) + 2 = 6」となり、出力は 6 になります。実際、6 は 2 で割り切れ、範囲 [2, 4] には含まれない最小の整数です。

このアルゴリズムは比較と四則演算のみで構成されているため、入力の値に関わらず常に O(1) の計算量で動作するのが特徴です。