C++で K mod P = 0 かつ Q mod K = 0 を満たす最小の数 K を求める方法

問題の概要

2つの整数 P と Q が与えられたとき、次の条件を同時に満たす最小の整数 K を求める問題を考えてみましょう。

K mod P = 0 かつ Q mod K = 0

そのような K が存在しない場合は -1 を出力します。

例えば、P = 2、Q = 8 の場合、答えは K = 2 となります。なぜなら、2 mod 2 = 0 であり、8 mod 2 = 0 というように、両方の条件を満たすからです。

解法の考え方

この問題の鍵となるのは、条件を整理することです。

• K mod P = 0 より、K は P の倍数である
• Q mod K = 0 より、K は Q の約数である

P の倍数の中で最小のものは P そのものです。したがって、P が Q の約数（つまり Q % P == 0）であれば、答えは必ず P になります。逆に Q が P で割り切れない場合は、条件を満たす K は存在しないため、-1 を出力すればよいことになります。

サンプルコード

#include<iostream>
using namespace std;
int getMinK(int p, int q) {
    if (q % p == 0)
        return p;
    return -1;
}
int main() {
    int p = 24, q = 48;
    cout << "Minimum value of K is: " << getMinK(p, q);
}

出力

Minimum value of K is: 24

コードの解説

関数 getMinK では、まず Q を P で割った余りが 0 かどうかを判定しています。割り切れる場合は P をそのまま返し、そうでなければ -1 を返します。

この例では P = 24、Q = 48 であり、48 % 24 == 0 が成り立つため、結果として 24 が出力されます。

計算量

このアルゴリズムは剰余演算を1回行うだけなので、時間計算量は O(1) となり、非常に効率的です。