C++でLCMとHCFが与えられたときにもう一方の数を求める方法

ある数Aと、その最小公倍数（LCM）および最大公約数（HCF/GCD）の値が与えられているとき、もう一方の数Bを求める問題を考えます。例えば、A = 5、LCM = 25、HCF = 4が与えられた場合、もう一方の数は20になります。

この問題を解く鍵となるのは、任意の2つの数AとBの間に常に成り立つ次の重要な数学的性質です。

$$𝐴∗𝐵=𝐿𝐶𝑀∗𝐻𝐶𝐹$$

つまり、「2つの数の積」は「最小公倍数と最大公約数の積」と等しくなります。この式をBについて変形すると、次のようになります。

$$𝐵= \frac{LCM*HCF}{A}$$

アルゴリズム

1. 数A、LCM、HCFの値を受け取ります。
2. LCMとHCFを掛け合わせ、その結果をAで割ります。
3. 計算結果をBとして返します。

コード例

#include <iostream>
using namespace std;
int anotherNumber(int A, int LCM, int GCD) {
   return (LCM * GCD) / A;
}
int main() {
   int A = 5, LCM = 25, GCD = 4;
   cout << "Another number is: " << anotherNumber(A, LCM, GCD);
}

出力

Another number is: 20

コードの解説

関数anotherNumberでは、引数として受け取ったLCMとGCDの積を計算し、それをAで割ることでBを求めています。この処理は1回の乗算と1回の除算だけで済むため、時間計算量はO(1)と非常に効率的です。

このように、LCMとHCFの基本的な性質を利用することで、複雑な探索を行わずとも、もう一方の数を簡単かつ高速に求めることができます。