Bài 17: Số học cơ bản - 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 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ừ tới kiểm tra nếu chia hết cho giá trị đó thì ta thu được một ước nguyên dương của .
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 :
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 nếu như có giá trị khoảng 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 dưới dạng với thì giá trị lớn nhất của là . Khi đó, giá trị chắc chắn phải bằng và hiển nhiên cả lẫn đều là ước của . Như vậy, chỉ cần đếm số lượng giá trị là có thể biết được 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;
// Lưu ý trường hợp n là số chính phương.
if (j != i)
++cnt;
}
return cnt;
}
Lúc này giải thuật có độ phức tạp giảm xuống còn và có thể sử dụng thoải mái cho các số
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à ) 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à ) 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, 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 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 với số nguyên và . 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ừ về và kiểm tra xem số đó có phải là ước của và hay không, nếu đúng như vậy thì số đó chính là . Đối với Bội chung nhỏ nhất, chỉ cần lấy tích của và chia cho ước chung lớn nhất của chúng. Độ phức tạp giải thuật là .
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ố và sử dụng phép trừ. Ý tưởng giải thuật như sau:
- Bước : Giả sử . Đặt cho tới khi thì chuyển qua bước .
- Bước : Khi đổi chỗ và rồi lặp lại bước cho tới khi .
- Bước : Khi đưa ra kết luận ước chung lớn nhất của hai số ban đầu chính là .
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 và 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 thì:
Dựa trên ý tưởng này, chỉ cần tiến hành đệ quy tới khi ước chung lớn nhất sẽ chính bằng . Độ phức tạp thuật toán là .
Cài đặt
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 số thực hiện như sau:
- Bước : Tìm ước chung lớn nhất của hai số đầu tiên
- Bước : Tiếp tục tìm của với rồi gán luôn vào sau đó tìm của và rồi gán vào $T,...$tiếp tục như vậy cho tới . Ta có công thức tổng quát:
Đối với bội chung nhỏ nhất của 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ố :
// Tìm ước chung lớn nhất của hai số.
int find_gcd(int A, int B)
{
if (B == 0)
return A;
else
return find_gcd(B, A % B);
}
// Tìm bội chung nhỏ nhất của hai số.
int find_lcm(int A, int B)
{
return A / find_gcd(A, B) * B;
}
// Tìm ước chung lớn nhất và bội chung nhỏ nhất của cả dãy số.
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 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
III. Tài liệu tham khảo
- https://en.wikipedia.org/wiki/Quadratic_residue
- https://en.wikipedia.org/wiki/Euler%27s_criterion
- https://vnoi.info/wiki/translate/he/So-hoc-Phan-1-Modulo-gcd.md
- https://vnoi.info/wiki/algo/math/modular-inverse.md
- https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
- https://en.wikipedia.org/wiki/Multiplicative_order
- https://vi.wikipedia.org/wiki/%C4%90%E1%BB%8Bnh_l%C3%BD_Euler
- https://www.geeksforgeeks.org/find-square-root-under-modulo-p-set-1-when-p-is-in-form-of-4i-3/
©️ Tác giả: Vũ Quế Lâm từ Viblo
All Rights Reserved