[PYTHON] Bestätigung der Grundlagen des Wettbewerbs professionell ~ gcd und lcm ~

Notieren Sie sich den Code, der verwendet wird, um die minimalen und maximalen Verpflichtungen (lcm) zu ermitteln, die bei der Wettbewerbsprogrammierung verwendet werden.

Für C ++

Im Fall von C ++ kann C ++ 17 unter der aktuellen Umgebung verwendet werden, sodass sich gcd und lcm in der numerischen Bibliothek befinden. Ich hatte Angst, dass lcm nicht überlaufen würde, aber sowohl gcc als auch clang scheinen eine Implementierung zu haben, die nicht überläuft.

Der Code kann intuitiv als "gcd (A, B)", "lcm (A, B)" mit der enthaltenen numerischen Bibliothek geschrieben werden.

Außerdem kann C ++ 17 ab sofort (23. Mai 2020) nicht in den alten Fragen der Vergangenheit verwendet werden. Daher sollten gcd und lcm wie folgt implementiert werden.

gcdlcm.cc

//min(x,y)Max, wenn kleiner oder gleich 0 ist(x,y)Ist zurück gekommen
//Implementiert basierend auf der euklidischen Methode der gegenseitigen Teilung
ll gcd(ll x,ll y){
    if(x<y) swap(x,y);
    //x ist immer größer
    ll r;
    while(y>0){
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}

//Achten Sie auf die Reihenfolge des Anrufs, um ein Überlaufen zu vermeiden
ll lcm(ll x,ll y){
    return ll(x/gcd(x,y))*y;
}

Für Python

Im Fall von Python kann die Version 3.8 unter der aktuellen Umgebung verwendet werden, sodass das Mathematikmodul gcd enthält. Ab sofort (23. Mai 2020) ist die alte Frage der Vergangenheit die Version 3.4 und das Fraktionsmodul enthält gcd. Seien Sie also vorsichtig. Außerdem ist lcm in keiner der beiden Versionen enthalten, sodass Sie es wie folgt selbst implementieren müssen.

gcdlcm.py

#In den alten Tagen aus itertools importieren gcd
#In diesem Fall aus Mathe importieren gcd
def lcm(a,b):
    return a//gcd(a,b)*b