Cho trước hai số nguyên không âm a và b, chúng ta phải tìm GCD của chúng (ước chung lớn nhất), tức là số lớn nhất là ước của cả hai a và b. Nó thường được ký hiệu là $gcd(a, b)$.

Và $Lcm(a, b) = a*b / gcd(a, b)$

Code:

// De quy
int gcd (int a, int b)
{
    return b ? gcd (b, a % b) : a;
}

//Khu de quy
int gcd (int a, int b)
{
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

// O(log(min(a, b))

int lcm (int a, int b)
{
    return a / gcd(a, b) * b;
}

Lưu ý rằng việc tối ưu hóa như vậy thường là không cần thiết nữa và hầu hết các ngôn ngữ lập trình đã có chức năng GCD trong thư viện chuẩn của chúng. Ví dụ: C ++ 17 có một chức năng như vậy std::gcdtrong numerictiêu đề.

Từ G ++17 trở đi ta có thể tính gcd, và lcm bằng cách:

__gcd(a, b);
lcm(a, b);

Ứng dụng:

Tính gcd và lcm

Problem kinh điểm

https://codeforces.com/contest/1165/problem/D

Problem luyện tập