C++で指定された3つの条件を満たす数aとbを見つける方法

整数 n が与えられたとき、以下の3つの条件をすべて満たす2つの数 a と b を見つけることを考えます。

• a mod b = 0(aがbで割り切れる)
• a * b > n(積がnより大きい)
• a / b < n(商がnより小さい)

条件を満たすペアが存在しない場合は、-1を出力します。

例として、n = 10 の場合、a = 90、b = 10 とすると、上記の3つの条件をすべて満たします。

解法のアプローチ

この問題は、次の手順で効率的に解くことができます。

• b = n と固定します。すると、a は残りの条件から導き出せます。
• a mod b = 0 となるのは、a が b の倍数のときです。
• a / b < n を満たすためには、a / b = n - 1(n - 1 は n より小さい)とすればよいことがわかります。
• したがって a = b × (n - 1) とすると、a * b > n も自動的に満たされます。

つまり、a = n × (n - 1)、b = n とすれば、3つの条件をすべて満たす解が得られます。

サンプルコード

#include<iostream>
using namespace std;
void findAandB(int n) {
    int b = n;
    int a = b * (n - 1);
    if (a * b > n && a / b < n) {
        cout << "a: " << a << endl;
        cout << "b: " << b;
    } else
        cout << -1 << endl;
}
int main() {
    int n = 10;
    findAandB(n);
}

実行結果

a: 90
b: 10

計算量について

この解法は、b を n に固定し、a を数式から直接求めるため、ループによる探索が不要です。そのため時間計算量は O(1) となり、非常に効率的です。n が大きくなっても即座に答えを計算できる点が大きなメリットです。