[PYTHON] Solution de programmation concurrentielle utilisant le produit du multiple commun minimum de a et b et du nombre commun maximum ab

Tirer parti du fait que le produit des promesses minimum et maximum des nombres naturels $ a et b $ est $ ab $ est utile lorsque la programmation de la concurrence a besoin de trouver le multiple commun minimum. Plus précisément, si le multiple commun minimum de $ a et b $ est $ l $ et la promesse maximale est $ g $, alors $ ab = gl $ est valable.

l = \frac{ab}{g}

Est le multiple commun minimum.

Par exemple, la réponse d'AtCoder ABC148 C --Snack est utile. Comme vous pouvez le voir dans l'énoncé du problème, trouver le multiple commun minimum est simplement un problème. En utilisant la formule ci-dessus, la réponse peut être écrite comme suit (la réponse est en 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)

Supplément: Preuve que le produit du multiple commun minimum de a et b et du nombre commun maximum est ab

Parce que $ a et b $ sont des multiples de $ g $

a = ga' \\
b = gb'

Il y a des nombres naturels $ a'et b '$ qui se satisfont. Aussi, parce que $ l $ est un multiple de $ a $

l = cga'

Il existe un nombre naturel $ c $ qui satisfait. De même,

l = dgb'

Il existe un nombre naturel $ d $ qui satisfait. De ces

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

, Et il s'avère que $ ca '$ est un multiple de $ b' $. Ici, $ c $ est un multiple de $ b '$ car $ a'et b' $ sont premiers l'un par rapport à l'autre. Puisque $ c $ est un facteur du multiple commun minimum $ l $, $ c = b '$. Donc

l = ga'b'

Est. Multipliez les deux côtés par $ g $

gl = ga'gb' \\
gl = ab

Est. Cela a été prouvé par ce qui précède.

Les références

[Standard] Produit d'engagement maximum et de multiple commun minimum | Note mathématique de Nakaken https://math.nakaken88.com/textbook/standard-product-of-greatest-common-divisor-and-least-common-multiple/# je