指定された条件を満たす2つの整数を求めるC++プログラムの解説

数値 x が与えられたとき、以下の条件をすべて満たす2つの整数 a と b を見つける問題を考えてみましょう。

• a と b はどちらも 1 以上 x 以下の範囲内にある
• a は b で割り切れる(a % b == 0)
• a × b > x が成り立つ
• a ÷ b < x が成り立つ

条件を満たす組み合わせが存在しない場合は -1 を返します。例えば x = 10 の場合、出力は 6 と 3 になります(他の組み合わせも正解となり得ます)。

シンプルな解法のポイント

この問題は実は非常にシンプルな解法があります。それは a = x、b = x とすることです。この選択が条件を満たすことを確認してみましょう。

• a は b で割り切れる:x ÷ x = 1 となるため成立
• a × b = x² は、x > 1 のとき必ず x より大きくなるため成立
• a ÷ b = 1 は、x > 1 のとき必ず x より小さくなるため成立

したがって、x ≥ 2 であれば常に a = b = x が正解となります。一方、x < 2(つまり x = 1)の場合は、a ÷ b = 1 となり「a ÷ b < x」の条件を満たせないため、-1 を出力します。

解法のアルゴリズム

1. x < 2 の場合は -1 を出力して終了する
2. それ以外の場合は x と x を出力する

C++での実装例

以下に実際の実装を示します。

#include <bits/stdc++.h>
using namespace std;
void solve(int x){
    if (x < 2){
        cout << -1;
        return;
    }
    cout << x << ", " << x;
}
int main(){
    int x = 10;
    solve(x);
}

入力例

10

出力例

10,10

まとめ

この問題は一見複雑な条件に思えますが、a と b をどちらも x にすることで、x ≥ 2 のすべてのケースで条件を満たせるという巧妙な性質を利用しています。計算量は O(1) であり、非常に効率的な解法です。