# Đồng dư và ước chung lớn nhất --- **Tác giả : [Dương Nguyên Khánh](https://github.com/kduongnguyen07)** ###### 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 ```C++ 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 ```C++ 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ứ =))