Confirmation des bases du concours professionnel ~ pgcd et lcm ~

Prenez note du code utilisé pour trouver les engagements minimum et maximum (lcm) utilisés dans la programmation des compétitions.

Pour C ++

Dans le cas de C ++, C ++ 17 peut être utilisé dans l'environnement actuel, donc gcd et lcm sont dans la bibliothèque numérique. J'avais peur que lcm ne déborde pas, mais gcc et clang semblent avoir une implémentation qui ne déborde pas.

Le code peut être écrit intuitivement comme «gcd (A, B)», «lcm (A, B)» avec la bibliothèque numérique incluse.

De plus, à partir de maintenant (23 mai 2020), C ++ 17 ne peut pas être utilisé dans les anciennes questions du passé, donc gcd et lcm doivent être implémentés comme suit.

gcdlcm.cc

//min(x,y)Max si est inférieur ou égal à 0(x,y)Est retourné
//Implémenté sur la base de la méthode de division mutuelle euclidienne
ll gcd(ll x,ll y){
    if(x<y) swap(x,y);
    //x est toujours plus grand
    ll r;
    while(y>0){
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}

//Faites attention à l'ordre d'appel pour ne pas déborder
ll lcm(ll x,ll y){
    return ll(x/gcd(x,y))*y;
}

Pour Python

Dans le cas de Python, la version 3.8 peut être utilisée dans l'environnement actuel, il y a donc gcd dans le module math. Aussi, à partir de maintenant (23 mai 2020), l'ancienne question passée est la version 3.4 et il y a pgcd dans le module des fractions, alors soyez prudent. De plus, lcm n'est inclus dans aucune des deux versions, vous devez donc l'implémenter vous-même comme suit.

gcdlcm.py

#Dans l'ancien temps de itertools import gcd
#Dans ce cas, à partir de l'importation mathématique gcd
def lcm(a,b):
    return a//gcd(a,b)*b