01.2.Modulo - GCD

Giới thiệu

Chúng ta tiếp tục chủ điểm thứ 2 trong chủ đề về lý thuyết số học, kiến thức chủ điểm này liên quan đến tính chất chia hết, chia dư, đồng dư thức, ước chung lớn nhất và bội chung nhỏ nhất. Là kiến thức cơ sở trong Toán học nhưng được ứng dụng rất nhiều trong Tin học, nhất là trong lý thuyết mật mã. Trong lập trình thi đấu, các kiến thức này được vận dụng để giải các dạng toán liên quan đến lý thuyết số học, Ad hoc Problems, tập hớp, quy hoạch động và nhiều dạng toán khác.

Modulo - Đồng dư thức

        Phép đồng dư thức cho bạn số dư của phép chia số này cho số khác. Trong hầu hết sách và tài liệu toán và Tin học, phép toán đồng dư thường được viết là MOD (viết tắt cho Modulo), trong ngôn ngữ lập trình C++, dấu của phép đồng dư là %.

Ví dụ:

Ta có hai số 5 và 2, khi đó 5%2 bằng 1 do khi chia 5 cho 2, ta được số dư là 1.

Tính chất: 

         Đồng dư thức có một số tính chất sau:

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

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

Ví dụ:

(5+3)%2 = (5%2 + 3%2)%2 = (1 + 1)%2 = 2%2 = 0

(5*3)%2 = (5%2 * 3%2)%2 = (1 * 1)%2 = 1%2 = 1

GCD - Ước chung lớn nhất

Ước chung lớn nhất (GCD, viết tắt của từ Greatest Common Divisor) của hai hay nhiều số là số nguyên dương lớn nhất mà là ước chung (common divisor) của tất cả các số đó.

Ví dụ: GCD của M = 15 và N = 12 là 3 vì 3 là số nguyên dương lớn nhất mà là ước chung của 15 và 12. 

Một cách tự nhiên nhất để tìm được ước chung lớn nhất theo định nghĩa như vậy là ta duyệt hết các số từ min(M, N) về 1, số đấu tiên mà cả M và N cùng chia hết là ước chung lớn nhất.

int gcd(int M, int N) {

    for (int i = min(M, N); i > 0; --i)

        if (M % i == 0 && N % i == 0) {

            return i;

        }

}

Nguồn code: VNOI

Độ phức tạp giải thuật O(min(M, N)

Độ phức tạp như trên dù tuyến tính nhưng vẫn chạy rất lâu với M, N rất lớn. Ngay từ thời cổ đại (khoảng 300BC), nhà toán học Hy Lạp Euclid đã đưa ra một giải thuật khác để tìm GCD của hau số M, N. Bằng cách lấy số lớn trừ số nhỏ rồi đặt kết quả dưới chân số lớn, viết lại số nhỏ. Cứ lặp lại quá trình này cho đến khi hai số bằng nhau thì đó là GCD.

int gcd(int M, int N) {

    while(M != N){

          if(M>N) M = M - N;

          else N = N - M;

    }

    return M; //return N cũng được vì lúc này M, N bằng nhau

}

Thuật toán trên có thể được minh họa như sau:

Trong trường hợp xấu nhất, độ phức tập giải thuật này vẫn là O(min(M, N))

Sau này, có một phiên bản cải tiến của thuật toán cổ đại này (chưa rõ mốc thời gian), thay vì dựa trên phép trừ, chúng ta lấy số lớn chia dư (modulo) cho số nhỏ sẽ khiến việc tiến gần đến GCD nhanh hơn.

int gcd(int M, int N) {

    if (N == 0) return M;

    else return gcd(N, M % N); //gọi đệ quy, dựa trên tính chất của GCD(M,N) = GCD(N, M%N)

}

Độ phức tạp giải thuật O(log max(M, N))

Ta cũng có thể khử đệ quy giải thuật trên như sau:

int GCD(int M, int N)

{

    while (N != 0)

    {

     int temp = M % N;

     M = N; N = temp;

    }

    return M;

}

Hoặc cũng có thể dùng hàm __GCD() có sẵn trong thư viện algorithm của C++

Bội chung nhỏ nhất

Bội số chung nhỏ nhất (BSCNN) của hai số là số nhỏ nhất mà chia hết cho hai số đó. Ví dụ, BCNN của 8 và 6 là 24.

Công thức tính:

Ví dụ:

BCNN(8,6) = (8/2)*6 = 4*6 = 24, trong đó 2 là UCLN(8,6) hay GCD(8,6)

Mở rộng

Đọc thêm về thuật toán Euclid mở rộng trên VNOI

Bài tập

Nhiệm vụ 1 - United We Stand (Codeforces)

Nguồn: https://codeforces.com/problemset/problem/1859/A

Tóm tắt:

Bạn được cho một dãy a có N phần tử. Hãy rãi các phần tử của a vào hai mảng trống b, c đảm bảo hai điều kiện:

• b và c không được trống

• mọi phần tử của c không phải ước của các phần tử của b

Xuất ra hai dãy b, c nếu có thể làm được như trên, nếu không, hãy xuất ra -1

Input:

• Mỗi test chứa nhiều testcase, dòng đầu tiên chứa số nguyên t (t <=500) là số lượng testcase

• Dòng đầu của mỗi test chứa số nguyên n (n<= 100) là số phần tử của dãy a

• Dòng thứ hai của mỗi test chứa n số nguyên a1, a2,...,an (ai <=10^9)

Output

Với mỗi testcase, nếu tạo được hai dãy b, c như mô tả thì xuất ra ba dòng:

• Dòng đầu chứa hai số nguyên lb, lc là chiều dài lần lược của b và c

• Dòng thứ hai xuất các phần tử dãy b

• Dòng thứ 3 xuất các phần tử dãy c

Nếu không thể tạo được b, c thì xuất -1

Ví dụ

Input:

5

3

2 2 2

5

1 2 3 4 5

3

1 3 5

7

1 7 7 2 9 1 4

5

4 8 12 12 4

Output:

-1

3 2

1 3 5 

2 4 

1 2

1 

3 5 

2 5

1 1 

2 4 7 7 9 

3 2

4 8 4 

12 12 

Giải thích:

• Test đầu không tạo được hai dãy b, c nên xuất ra -1

• Test thứ hai tạo được b = [1, 2, 3], c = [4, 5], rõ ràng 4, 5 không phải ước của 1, 2 hay 3

Nhiệm vụ 2 - Chia bánh (LQĐ Online Jugle)

Nguồn: https://lqdoj.edu.vn/problem/share

Tóm tắt:

Bạn muốn chia 𝑛 cái bánh cho 𝑚 người, ban đầu mỗi cái bánh là một phần. Công cụ duy nhất bạn có là một dao cắt bánh, ở mỗi thao tác cắt, bạn được chia một phần bánh thành 2 phần với tỉ lệ tùy ý. Hãy tìm cách dùng ít thao tác cắt nhất để chia bánh thành các phần chia cho  𝑚 người, mỗi phần thuộc về đúng một người và lượng bánh mỗi người được nhận là bằng nhau. 

Input:

• Gồm một dòng duy nhất chứa hai số nguyên m, n <=10^8

Output:

• Ghi ra một số nguyên duy nhất là số thao tác cắt phải sử dụng

Ví dụ:

input:

3 5

Output:

4

Nhiệm vụ 3 - Ước số chung (LQĐ Online Jugle)

Nguồn: https://lqdoj.edu.vn/problem/w06

Tóm tắt:

Nhập vào hai số nguyên dương m, n. Xuất ra tất cả các ước chung của chúng. Ước chung là số mà cả m, n cùng chia hết.

Input:

• Một dòng duy nhất chứa hai số nguyên dương m, n (m, n <=10^7)

Output:

• Một dòng duy nhất là danh sách các ước chung của m, n. Mỗi số cách nhau một khoảng trắng

Ví dụ:

Input:

54   72

Output:

1 2 3 4 6 9 18

Nhiệm vụ 4 - MAXSUMDIV - ĐẾM BỘI  (Vĩnh Định Coder)

Nguồn: https://vinhdinhcoder.net/Problem/Details/4656?fbclid=IwAR0ie4O1lD2-o78JgJXrjvsnvXFV1ZxCGEnTcjx1cSyvIb74Z8xNwcsTsyc

Tóm tắt:

Số tự nhiên a chia hết cho số tự nhiên b thì ta nói a là bội của b, còn b là ước của a. Ví dụ các bội số của 2 là: 2, 4, 6, 8 …

          Bạn được cho 5 số nguyên dương n, a, b, x và y: Khi xem xét các số tự nhiên U thuộc vào đoạn [1, n]: Bạn có thể chọn cách xử lý U thuộc một trong ba trường hợp sau:

          + Nếu U là bội của a thì bạn được nhận được x đồng.

          + Nếu U là bội của b thì bạn được nhận được y đồng.

          + Nếu U là bội của cả a và b thì bạn được nhận được max(x, y) đồng.

          Hỏi nếu xét hết các số nguyên trong đoạn [1, n] thì lợi nhuận tối đa bạn thu được là bao nhiêu? Bạn cần viết chương trình nhận đầu vào là 5 số nguyên nói trên, tính và thông báo lợi nhuận tối đa bạn nhận được.

Dữ liệu nhập:

  - Gồm 5 số nguyên dương (0 ≤ n, a, b, x, y ≤ 10^9)

Kết quả:

  - Một số nguyên duy nhất là lợi nhuận lớn nhất thu được.

Ví dụ:

Input:

3 1 2 3 4

Output:

10

Nhiệm vụ 5 - GCDALTN - GCD LUỸ THỪA (vinhdinhcoder)

Nguồn: https://vinhdinhcoder.net/Problem/Details/4663

Tóm tắt:
Cho a,b,n
Tính gcd(a^n,b)

Dữ liệu nhập:

  - Chứa 3 số nguyên A, B, N ( 1 ≤ A, B, N ≤ 109)

Kết quả:

  - Một dòng duy nhất là GCD thu được

Ví dụ:

Input:
2 3 3

Output:
1

Nhiệm vụ 6:  K-divisible Sequence (lqdoj)

Nguồn: https://lqdoj.edu.vn/problem/kdivseq

Tóm tắt:

Ví dụ:

Input:
1
6 9

Output:
2 5 7 3 10 9