[PYTHON] Competitive programming solution using that the product of the least common multiple of a and b and the greatest common divisor is ab

Taking advantage of the fact that the product of the least common multiple and the greatest common divisor of the natural numbers $ a and b $ is $ ab $ is useful when competitive programming needs to find the least common multiple. Specifically, if the least common multiple of $ a and b $ is $ l $ and the greatest common divisor is $ g $, then $ ab = gl $ holds.

l = \frac{ab}{g}

Is the least common multiple.

For example, the answer to AtCoder's ABC148 C --Snack is useful. As you can see from the problem statement, it is simply a problem to find the least common multiple. Using the above formula, the answer can be written as follows (the answer is in Python).

def gcd(a, b):
    while a:
        a, b = b % a, a
    return b

A, B = map(int, input().split())
print(A // gcd(A, B) * B)

Supplement: Proof that the product of the least common multiple and the greatest common divisor of a and b is ab

Because both $ a and b $ are multiples of $ g $

a = ga' \\
b = gb'

There are coprime natural numbers $ a'and b'$ that satisfy. Also, because $ l $ is a multiple of $ a $

l = cga'

There exists a natural number $ c $ that satisfies. Similarly,

l = dgb'

There exists a natural number $ d $ that satisfies. From these

cga' = dgb' \\
ca' = db' \\

, And it turns out that $ ca'$ is a multiple of $ b'$. Here, $ c $ is a multiple of $ b'$ because $ a'and b'$ are relatively prime. Since $ c $ is a factor of the least common multiple $ l $, $ c = b'$. Therefore

l = ga'b'

Is. Multiply both sides by $ g $

gl = ga'gb' \\
gl = ab

Is. It was proved from the above.

References

[Standard] Product of greatest common divisor and least common multiple | Nakaken's math note https://math.nakaken88.com/textbook/standard-product-of-greatest-common-divisor-and-least-common-multiple/# i