欧几里得算法

用来求最大公约数，又称辗转相除法，时间复杂度可以认为是O(lgn)

gcd( a , b ) = gcd( b , a % b )

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

最小公倍数

lcm ( a, b) = a * b / gca( a, b )

Last modification：September 19th, 2019 at 01:10 am

如果觉得我的文章对你有用，请随意赞赏

Comment *

私密评论

Name *

🎲

Email *

Site

子不语 • 2019 年 09 月 19 日

用来求最大公约数，又称辗转相除法，时间复杂度可以认为是O(lgn)

gcd( a , b ) = gcd( b , a % b )

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a%b);
}

最小公倍数

lcm ( a, b) = a * b / gca( a, b )