C++で一方の数で割り切れ、もう一方の数を割り切る最小の数を求める方法

問題文

2つの整数 p と q が与えられたとき、次の2つの条件を同時に満たす最小の数 x を求めることが課題です。

• q % x = 0（x は q を割り切る）
• x % p = 0（x は p で割り切れる）

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

具体例

p = 3、q = 66 の場合、答えは 3 となります。
66 % 3 = 0
3 % 3 = 0

アルゴリズムの考え方

この問題は、数学的な性質を使うことで非常にシンプルに解くことができます。

• ある数 x が条件を満たすならば、x は p の倍数であり、かつ q は x の倍数です。したがって、q は必ず p で割り切れることになります（q % p = 0）。
• 逆に言えば、q が p で割り切れない場合には、条件を満たす数は一切存在しないため、-1 を返せばよいことになります。
• q % p = 0 が成り立つ場合、条件を満たす最小の x は「p と q の最大公約数（GCD）」となります。これは、x が p の約数でありながら q の約数でもある必要があるためです。

C++での実装例

以下は、上記のアルゴリズムを実装したC++のコードです。__gcd 関数はGCCで提供されている組み込み関数で、2つの整数の最大公約数を求めることができます。

#include <bits/stdc++.h>
using namespace std;

int getMinValue(int p, int q) {
    if (q % p == 0) {
        return __gcd(p, q);
    }
    return -1;
}

int main() {
    int p = 3;
    int q = 66;
    cout << "Minimum value = " << getMinValue(p, q) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Minimum value = 3

計算量について

この解法の計算量は、ユークリッドの互除法によるGCD計算に依存し、O(log(min(p, q))) となります。そのため、非常に大きな数が与えられても高速に動作する効率的なアルゴリズムです。