C++で (x % k) × (x / k) == n を満たす最小の x を求める方法

2つの正の整数 n と k が与えられたとき、(x % k) × (x / k) が n と等しくなるような正の整数 x を求める必要があります。例えば n = 4、k = 6 の場合、答えは 10 になります。実際に確認すると、(10 % 6) × (10 / 6) = 4 × 1 = 4 となり、条件を満たしています。

解法のアプローチ

ここでポイントになるのは、x % k の値が必ず 1 以上 k − 1 以下の範囲に収まるという点です（0 は除外します。x % k が 0 になると積も 0 になり、正の整数 n とは一致しないためです）。

そこで、n の約数のうち [1, k − 1] の範囲に含まれるものをすべて列挙し、それぞれを x % k の候補として試します。x % k の値を rem とすると、x / k = n / rem が成り立つため、x は次の式で表せます。

x = (n / rem) × k + rem

考えられるすべての候補の中から最小の x を選べば、それが求める答えとなります。

例

#include<iostream>
using namespace std;
int minValue(int x, int y){
    return (x > y)?y:x;
}
int getX(int n, int k) {
    int x = INT_MAX;
    for (int rem = k - 1; rem > 0; rem--) {
        if (n % rem == 0)
            x = minValue(x, rem + (n / rem) * k);
    }
    return x;
}
int main() {
    int n = 4, k = 6;
    cout << "The minimum value of x: " << getX(n, k);
}

出力

The minimum value of x: 10

コードの解説

関数 getX では、rem を k − 1 から 1 まで降順に走査します。n が rem で割り切れる場合（rem が n の約数である場合）に、x = rem + (n / rem) × k を計算し、現在の最小値と比較して小さい方を保持します。計算量は O(k) で、k がそれほど大きくない場合に効率的に動作します。

なお、n = 4、k = 6 の場合、[1, 5] の範囲に含まれる 4 の約数は 1、2、4 の 3 つです。rem = 4 のとき x = 4 + 1 × 6 = 10、rem = 2 のとき x = 2 + 2 × 6 = 14、rem = 1 のとき x = 1 + 4 × 6 = 25 となるため、最小値は 10 になります。