[PYTHON] Confirmation of basics of competition professionals ~ gcd and lcm ~

Make a note of the code used to find the least common multiple (gcd) and greatest common divisor (lcm) used in competitive programming.

For C ++

In the case of C ++, C ++ 17 can be used under the current environment, so gcd and lcm are in the numeric library. I was worried that lcm would not overflow, but both gcc and clang seem to have an implementation that does not overflow.

The code can be intuitively written as gcd (A, B), lcm (A, B) with the inclusion of the numeric library.

Also, as of now (May 23, 2020), C ++ 17 cannot be used in the old past questions, so gcd and lcm should be implemented as follows.

gcdlcm.cc

//min(x,y)Max if is less than or equal to 0(x,y)Is returned
//Implemented based on Euclidean algorithm
ll gcd(ll x,ll y){
    if(x<y) swap(x,y);
    //x is always larger
    ll r;
    while(y>0){
        r=x%y;
        x=y;
        y=r;
    }
    return x;
}

//Be careful about the order of calling so as not to overflow
ll lcm(ll x,ll y){
    return ll(x/gcd(x,y))*y;
}

For Python

In the case of Python, the version 3.8 can be used under the current environment, so there is gcd in the math module. Also, as of now (May 23, 2020), the old past question is version 3.4 and there is gcd in the fractions module, so be careful. Also, lcm is not included in either version, so you need to implement it yourself as follows.

gcdlcm.py

#In the old days from itertools import gcd
#In this case from math import gcd
def lcm(a,b):
    return a//gcd(a,b)*b