結構、そのまんまな問題が来ましたね。
問題概要
2 つの正の整数 が与えられる。
でも でも割り切れる正の整数のうち、最小の値を求めよ。
制約
考えたこと
すごくそのまんまですね。 と の最小公倍数を求めよ、という問題。実は と の最大公約数を 、最小公倍数を とすると
が成立します。たとえば、 と の最大公約数は 2、最小公倍数は 12 ですが、
となっています。つまり、この問題は
- と の最大公約数を求める ( とする)
- を答える
とすればよいです。多少の工夫点として、計算する順番は
A * B / G
とするのではなく、
A / G * B
とすると、オーバーフローのリスクが少し減ります。 は の約数なので、 は必ず割り切れます。
#include <iostream> using namespace std; long long GCD(long long x, long long y) { return (y ? GCD(y, x%y) : x); } int main() { long long A, B; cin >> A >> B; long long G = GCD(A, B); cout << A/G * B << endl; }