【C++】指定された範囲内で x が y を割り切るペア（x, y）を O(1) で見つける方法

今回は興味深いアルゴリズムの問題を取り上げます。範囲 l ≤ x, y ≤ r を満たすペア（x, y）を見つけるというもので、このペアには「x が y を割り切る」という性質が必要です。条件を満たすペアが複数存在する場合は、そのうちの 1 つを出力すればよいことになっています。

解法のアイデア

この問題は、実は O(1) の計算量で解くことができます。鍵となるのは、下限値 l とその 2 倍の値 2l です。

その理由を考えてみましょう。y/x の最小値は 2 です。もし範囲内により大きな値（y/x ≥ 3 となる組み合わせ）が存在するなら、必ず y/x = 2 となる組み合わせも同じ範囲内に存在します。また、x を大きくすれば 2x もそれに伴って大きくなるため、範囲内に収まる最小のペアは必ず (l, 2l) になります。

したがって、2l ≤ r が成り立つならば (l, 2l) が答えとなり、それ以外の場合は条件を満たすペアは存在しません。

実装例（C++）

#include<iostream>
using namespace std;

void getPair(int l, int r) {
    int x = l;
    int y = 2 * l;
    cout << "(" << x << ", " << y << ")" << endl;
}

int main() {
    int l = 3, r = 6;
    getPair(l, r);
}

実行結果

(3, 6)

まとめ

この問題は一見すると範囲内の全組み合わせを調べる必要がありそうですが、「x が y を割り切る」という条件と「y/x の最小値は 2」という性質を利用することで、定数時間で答えを導き出せます。範囲の下限 l と 2l の関係を確認するだけでよいため、非常に効率的な解法といえます。