+4

Tìm các ước của một số nguyên dương và GCD - LCM

I. Tìm các ước của một số nguyên dương

1. Giải thuật ngây thơ

Để tìm tất cả các ước nguyên dương của một số nguyên dương N,N, phương pháp dễ nhất là sử dụng một vòng lặp, duyệt qua toàn bộ các giá trị từ 11 tới N,N, kiểm tra nếu NN chia hết cho giá trị đó thì ta thu được một ước nguyên dương của NN.

Cài đặt: Dưới đây là cài đặt đếm số lượng ước nguyên dương của một số nguyên dương NN:

int count_divisors(int N)
{
    int cnt = 0;
    for (int i = 1; i <= N; ++i)
        if (N % i == 0)
            cnt++;

    return cnt;
}

Dễ dàng nhận thấy giải thuật có độ phức tạp O(N),O(N), nếu như NN có giá trị khoảng 10810^8 trở lên sẽ không thể đảm bảo tốc độ thực thi trong khoảng $1$s. Ta cần một giải thuật tốt hơn!

2. Cải tiến giải thuật

Ta có một nhận xét như sau: Giả sử viết được NN dưới dạng N=i×jN = i \times j với ij,i \le j, thì giá trị lớn nhất của iiN\sqrt{N}. Khi đó, giá trị jj chắc chắn phải bằng Ni,\frac{N}{i}, và hiển nhiên cả ii lẫn jj đều là ước của NN. Như vậy, chỉ cần đếm số lượng giá trị ii là có thể biết được NN có bao nhiêu ước nguyên dương:

int count_divisors(int N)
{
    int cnt = 0;
    for (int i = 1; i * i<= N; ++i)
        if (N % i == 0)
        {
            ++cnt;

            int j = N / i;
            if (j != i)  // Cần xét trường hợp đặc biệt nếu N là số chính phương thì có thể i = j
		++cnt;
        }

    return cnt;
}

Lúc này giải thuật có độ phức tạp giảm xuống còn O(N),O(\sqrt{N}), và có thể sử dụng thoải mái cho các số N1015!N \le 10^{15}!

II. Ước chung lớn nhất và Bội chung nhỏ nhất

1. Giới thiệu

Ước chung lớn nhất (Greatest Common Divisor – viết tắt là GCD\text{GCD}) của hai hay nhiều số là số nguyên dương lớn nhất mà là ước chung của tất cả các số đó. Bội chung nhỏ nhất (Lowest Common Multiple – viết tắt là LCM\text{LCM}) của hai hay nhiều số là số nguyên dương nhỏ nhất mà là bội chung của tất cả các số đó. Trong lập trình thi đấu, GCD - LCM\text{GCD - LCM} là chủ đề rất được yêu thích trong mảng số học và đòi hỏi người lập trình có cái nhìn sâu sắc, kiến thức toán học tốt để giải quyết các vấn đề số học. Có hai cách để giải quyết bài toán liên quan tới GCD - LCM\text{GCD - LCM}, một là sử dụng "duyệt trâu" (Giải thuật “ngây thơ”), hai là sử dụng giải thuật Euclid. Dưới đây sẽ trình bày các giải thuật tìm GCD - LCM\text{GCD - LCM} với 22 số nguyên AABB. Các cài đặt sẽ sử dụng ngôn ngữ C++ theo phong cách lập trình của người viết, bạn đọc hoàn toàn có thể chỉnh sửa theo ý mình để thu được những cài đặt đẹp mắt hơn.

2. Giải thuật ngây thơ

Tiến hành duyệt tất cả các số từ min⁡(A,B)\text{min}⁡(A,B) về 11 và kiểm tra xem số đó có phải là ước của AABB hay không, nếu đúng như vậy thì số đó chính là GCD(A,B)\text{GCD}(A,B). Đối với Bội chung nhỏ nhất, chỉ cần lấy tích của AABB chia cho ước chung lớn nhất của chúng. Độ phức tạp giải thuật là O(min(A,B))O(\text{min}(A,B)).

long long find_gcd(long long A, long long B)
{
    for (long long i = min(A, B); i > 0; --i)
        if (A % i == 0 && B % i == 0)
            return i;
}

long long find_lcm(long long A, long long B)
{
    return (A / gcd(A, B)) * B;
}

3. Giải thuật Euclid

3.1. Giải thuật cơ sở

Từ bậc trung học cơ sở, các bạn có lẽ đã biết đến giải thuật tìm ước chung lớn nhất của hai số AABB sử dụng phép trừ. Ý tưởng giải thuật như sau:

  • Bước 11: Giả sử A>BA > B. Đặt A=ABA = A - B cho tới khi A<BA < B thì chuyển qua bước 22.
  • Bước 22: Khi A<B,A < B, đổi chỗ AABB rồi lặp lại bước 11 cho tới khi A=BA = B.
  • Bước 33: Khi A=B,A = B, đưa ra kết luận ước chung lớn nhất của hai số ban đầu chính là AA.

Cài đặt:

int find_gcd(int A, int B)
{
    // Trường hợp đặc biệt: A = 0 thì gcd(A, B) = B, ngược lại B = 0 thì gcd(A, B) = A.
    if (A == 0)
        return B;
    else if (B == 0)
        return A;

    while (A != B)
    {
        if (A > B)
            A -= B;
    	else 
	    B -= A;
    }

    return A;
}

3.2. Giải thuât Euclid

Giải thuật cơ sở trên có một nhược điểm, đó là nếu AABB lớn thì việc thực hiện phép trừ sẽ diễn ra rất lâu, dẫn đến không đáp ứng độ phức tạp thuật toán. Để cải tiến nó, ta có thể áp dụng giải thuật Euclid. Giải thuật dựa trên một tính chất của ước chung lớn nhất như sau: Nếu A=B.q+rA = B.q + r thì:

GCD(A,B)=GCD(B,A % B)\text{GCD}(A,B)=\text{GCD}(B,A \ \% \ B)

Dựa trên ý tưởng này, chỉ cần tiến hành đệ quy tới khi A % B=0A \ \% \ B=0, ước chung lớn nhất sẽ chính bằng AA. Độ phức tạp thuật toán là O(log(max⁡(A,B)))O(\log(\text{max}⁡(A,B))).

long long gcd_euclid(long long A, long long B)
{
    if (B == 0)
        return A;
    else 
        return gcd_euclid(B, A % B);
}

Ngoài ra, trong thư viện STL của C++ cung cấp một hàm tìm ước chung lớn nhất của hai số nguyên là __gcd(a, b) với độ phức tạp giống như giải thuật Euclid. Để sử dụng nó, bạn cần khai báo thư viện <algorithm>. Lấy ví dụ:

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int a = 5, b = 10;
    cout << "Ước chung lớn nhất của 5 và 10 là: " << __gcd(a, b);

    return 0;
}

Kết quả đoạn chương trình trên sẽ là:

Ước chung lớn nhất của 5 và 10 là: 5

4. Tìm ước chung lớn nhất và bội chung nhỏ nhất của nhiều số

Để tìm ước chung lớn nhất của dãy số gồm NN số (N3)(N \ge 3), thực hiện như sau:

  • Bước 11: Tìm ước chung lớn nhất của hai số đầu tiên

T=GCD(a1,a2)T = \text{GCD}(a_1, a_2)

  • Bước 22: Tiếp tục tìm GCD\text{GCD} của a3a_3 với TT rồi gán luôn vào T,T, sau đó tìm GCD\text{GCD} của a4a_4TT rồi gán vào $T,...$tiếp tục như vậy cho tới aNa_N. Ta có công thức tổng quát:

GCD(a1,a2,...,aN)=GCD(GCD(GCD(GCD(a1,a2),a3),a4,..),aN)\text{GCD}(a_1, a_2,...,a_N) = \text{GCD}(\text{GCD}(\text{GCD}(\text{GCD}(a_1, a_2), a_3), a_4,..),a_N)

Đối với bội chung nhỏ nhất của NN số, cách tìm hoàn toàn tương tự với ước chung lớn nhất. Cài đặt dưới đây sẽ tìm ước chung lớn nhất và bội chung nhỏ nhất của một dãy số a1,a2,...,aNa_1, a_2,..., a_N:

int find_gcd(int A, int B) // Tìm ước chung lớn nhất của hai số.
{
    if (B == 0)
        return A;
    else 
        return find_gcd(B, A % B);   
}

int find_lcm(int A, int B) // Tìm bội chung nhỏ nhất của hai số.
{
    return A / find_gcd(A, B) * B;
}

void gcd_lcm_seq(int N, int a[])
{
    int gcd_all = find_gcd(a[1], a[2]), lcm_all = find_lcm(a[1], a[2]);
    for (int i = 3; i <= N; ++i)
    {
    gcd_all = find_gcd(gcd_all, a[i]);
    lcm_all = find_lcm(lcm_all, a[i]);
    }

   cout << "Ước chung lớn nhất của cả dãy là: " << gcd_all << endl;
   cout << "Bội chung nhỏ nhất của cả dãy là: " << lcm_all;
}

Chạy chương trình trên với dãy a={12,8,10,4,6},a = \{12, 8, 10, 4, 6\}, ta thu được kết quả là:

Ước chung lớn nhất của cả dãy là: 2
Bội chung nhỏ nhất của cả dãy là: 360

5. Giải thuật Euclid mở rộng

GCD(A,B)\text{GCD}(A,B) có một tính chất là luôn có thể biểu diễn dưới dạng phương trình:

Ax+By=GCD(A,B) (1)Ax+By=\text{GCD}(A,B) \ (1)

Giải thuật Euclid mở rộng sử dụng để tìm một cặp số nguyên (x,y)(x,y) thỏa mãn phương trình trên, và còn dùng để tính nghịch đảo modulo (mình sẽ nói tới ở phần sau). Cặp số (x,y)(x,y) có thể có giá trị âm, hoặc bằng 00 đều được. Dưới đây mình sẽ trình bày giải thuật tìm GCD(A,B)\text{GCD}(A,B) và một cặp (x,y)(x,y) thỏa mãn phương trình.

long long d, x, y; // UCLN và cặp nghiệm (x, y).

void extended_euclid(long long A, long long B)
{
    if (B == 0)
    {
        x = 1;
        y = 0;
        d = A;
    }
    else
    {
        extended_euclid(B, A % B);
        long long temp = x;
        x = y;
        y = temp – (A / B) * y;
    }
}

int main()
{
    cin >> A >> B;
    extended_euclid(A, B);
    cout << d << ' ' << x << ‘  ‘ << y;
    return 0;
}

Cơ chế của giải thuật như sau: Ban đầu chương trình thực thi giống giải thuật Euclid, tới khi B=0,B=0, khi đó ta sẽ có AA là ước chung lớn nhất của AAB,B, sau đó đặt x=1,y=0x=1,y=0. Bởi vì B=0B=0 và hiện tại GCD(A,B)=A\text{GCD}(A,B)=A nên phương trình (1)(1) trở thành:

A.1+0.0=AA.1+0.0=A

Sau đó chương trình gọi lại các lệnh dưới lời gọi đệ quy để tìm ra xxyy. Chứng minh:

  • Sau khi gọi đệ quy, phương trình ở bước tiếp theo của giải thuật là:

B.x+(A%B).y=GCD(A,B) (2)B.x+(A \% B).y=\text{GCD}(A,B) \ (2)

  • Thay A % B=AAB.BA \ \% \ B=A-\left \lfloor{\frac{A}{B}} \right \rfloor .B, phương trình (2)(2) trở thành:
B.x+(A-\left \lfloor{\frac{A}{B}} \right \rfloor.B).y=\text{GCD}(A,B)$$ $$\Leftrightarrow A.y+B.(x-\left \lfloor{\frac{A}{B}} \right \rfloor.y)=\text{GCD}(A,B)
  • Từ đây được công thức đệ quy:

x=y;y=xAB.yx' = y; y' = x - \left \lfloor{\frac{A}{B}} \right \rfloor.y

  • Như vậy từ bước cơ bản x=1,y=0;x=1,y=0; chương trình sẽ tiếp tục tính ngược lên để ra được x,yx,y thỏa mãn phương trình ban đầu. Độ phức tạp giải thuật là O(log(max⁡(A,B)))O(\log(\text{max}⁡(A,B))).

Ngoài ra, giải thuật Euclid mở rộng còn có thể sử dụng để giải phương trình Diophantine tuyến tính, sẽ được đề cập tới ở một bài viết khác.

Tài liệu tham khảo


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí