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

Recommended Posts

Confirmation des bases du concours professionnel ~ pgcd et lcm ~
[Pour les professionnels de la concurrence] Résumé du doublement
Organiser la bibliothèque des professionnels du concours ~ Liste des numéros environ ~
Confirmation des questions de base du professionnel de la concurrence ~ Recherche dichotomisée ~
[Python] Chapitre 02-01 Bases des programmes Python (opérations et variables)
Les bases de Python ①
Bases de python ①
Disposition de la bibliothèque professionnelle de concours ~ Équation indéfinie linéaire bidimensionnelle ~
J'ai lu "Bases des circuits électriques et des lignes de transmission"
Bases et mécanismes du signal Linux (à partir du noyau v5.5)
Animer les bases de la planification dynamique et des problèmes de sac à dos