Đồng dư và ước chung lớn nhất

---

Tác giả : Dương Nguyên Khánh

tags:Number Theory

Mở đầu

Các bài toán trong lập trình thi đấu (competitive programming) mà liên quan đến Toán học thường sẽ rơi vào hai mảng là số học (number theory) và hình học. Nếu bạn biết nhiều về số học, bạn sẽ có khả năng giải quyết nhiều bài toán khó và một nền tảng tốt để giải quyết nhiều bài toán khác.

Khái niệm

Đồng dư là số dư khi chia số này cho số kia hay còn biết với toán tử %

Kiến thức về đồng dư

(a+b)%c=(a%c+b%c)%c
(a.b)%c=((a%c).(b%c))%

Ước chung lớn nhất

Quy ước : gcd(a,b) là ước chung lớn nhất của a,b lcm(a,b) là bội chung nhỏ nhất
Có nhiều cách để tìm ước chung lớn nhất nhưng có 2 cách phổ biến là chạy trâu và thuật toán Euclid

Chạy trâu

int gcd(int A, int B) {
    for (int i = min(A, B); i > 0; --i)
        if (A % i == 0 && B % i == 0) {
            return i;
        }
}
/*
Đây thực ra là một cách khá là đần nhưng độ phức tạp là O(min(a,b))
*/

Thuật toán Euclid

Thuật toán Euclid dựa trên tính chất sau của ước chung lớn 
nhất GCD(A,B)=GCD(B,A%B). Thuật toán sẽ quy nạp cho đến khi A%B=0 
Tương tự __gcd(a,b)

Cài đặt thuật toán

int gcd(int A, int B) {
    if (B == 0) return A;
    else return gcd(B, A % B);
}

Nhận xét :Kiến thức toán cũng giúp ích được đấy chứ =))