[PYTHON] Wettbewerbsfähige Programmierlösung, bei der das Produkt aus dem minimalen gemeinsamen Vielfachen von a und b und der maximalen gemeinsamen Anzahl ab ist

Die Tatsache auszunutzen, dass das Produkt der minimalen und maximalen Versprechen der natürlichen Zahlen $ a und b $ $ ab $ ist, ist nützlich, wenn die Wettbewerbsprogrammierung das minimale gemeinsame Vielfache finden muss. Insbesondere wenn das minimale gemeinsame Vielfache von $ a und b $ $ l $ ist und das maximale Versprechen $ g $ ist, dann gilt $ ab = gl $.

l = \frac{ab}{g}

Ist das minimale gemeinsame Vielfache.

Beispielsweise ist die Antwort von AtCoders ABC148 C - Snack hilfreich. Wie Sie der Problemstellung entnehmen können, ist es einfach ein Problem, das minimale gemeinsame Vielfache zu finden. Mit der obigen Formel kann die Antwort wie folgt geschrieben werden (die Antwort ist 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)

Ergänzung: Beweis, dass das Produkt aus dem minimalen gemeinsamen Vielfachen von a und b und der maximalen gemeinsamen Zahl ab ist

Weil sowohl $ a als auch b $ ein Vielfaches von $ g $ sind

a = ga' \\
b = gb'

Es gibt natürliche Zahlen $ a ', b' $, die sich gegenseitig ausschließen und erfüllen. Auch weil $ l $ ein Vielfaches von $ a $ ist

l = cga'

Es gibt eine natürliche Zahl $ c $, die erfüllt. Ähnlich,

l = dgb'

Es gibt eine natürliche Zahl $ d $, die erfüllt. Von diesen

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

Und es stellt sich heraus, dass $ ca '$ ein Vielfaches von $ b' $ ist. Hier ist $ c $ ein Vielfaches von $ b '$, weil $ a'und b' $ Primzahlen zueinander sind. Da $ c $ ein Faktor des minimalen gemeinsamen Vielfachen $ l $ ist, ist $ c = b '$. Deshalb

l = ga'b'

Ist. Multiplizieren Sie beide Seiten mit $ g $

gl = ga'gb' \\
gl = ab

Ist. Es wurde von oben bewiesen.

Verweise

[Standard] Produkt mit maximalem Engagement und minimalem gemeinsamen Vielfachen | Nakakens mathematischer Hinweis https://math.nakaken88.com/textbook/standard-product-of-greatest-common-divisor-and-least-common-multiple/# ich