Ước, bội, ƯCLN, BCNN
- Độ khó
- ★★☆☆☆ Dễ
- Thời lượng
- Khoảng 90 phút
- Học trước
- Mảng 1 chiều
- Chủ đề
- số họcước và bội
- Trạng thái
Kiến thức cơ bản
Ước số, bội số
Số d là ước của n nếu n chia hết cho d, tức n%d == 0. Ví dụ các ước của 12 là 1, 2, 3, 4, 6, 12.
Cách đơn giản in tất cả các ước d của n.
for (int d = 1; d <= n; ++d) {
if (n%d == 0) cout <<d << " ";
}
Nhưng lưu ý rằng các ước luôn đi thành từng cặp (d, n/d), nếu d là ước của n thì n/d cũng là ước của n. Khi đó ta chỉ cần duyệt đến căn bậc hai của n.
for (int d = 1; d*d <= n; ++d) {
if (n%d == 0) {
cout <<d <<" "; // ước nhỏ
if (d != n/d) cout <<n/d <<" "; // ước lớn
}
}
Số m là bội của k nếu m chia hết cho k, Ví dụ các bội của 3 là 3, 6, 9, 12, 15, ... (có vô số bội).
Ước chung lớn nhất
Ước chung lớn nhất của hai hay nhiều số là số lớn nhất trong tập hợp các ước chung của các số đó.
Ví dụ: tập hợp các ước của 4 là U(4) = {-1; -2; -4; 1; 2; 4}, tập hợp các ước của 6 là U(6) = {-1; -2; -3; -6; 1; 2; 3; 6}, nên ước chung của 4 và 6 là {-1; -2; 1; 2}. Vậy ước chung lớn nhất của 4 và 6 là 2 hay (4, 6) = 2.
Ta kí hiệu (a, b, c,...) hoặc ucln(a, b, c,...) hoặc gcd(a, b, c,...) thay cho việc gọi ước chung lớn nhất của các số a, b, c,... ("greatest common divisor − gcd" là cụm từ tiếng anh nghĩa là ước chung lớn nhất).
Thuật toán Euclid để tìm ước chung lớn nhất của hai số a, b:
- Tìm số dư (r) của phép chia a cho b.
- Nếu r = 0, thì ucln(a, b) = b, ngược lại (r > 0) thì ucln(a, b) = ucln(b, r).
Ví dụ: tìm ucln(48, 18). Vì 48 chia 18 được 2 dư 12 (48 = 18.2 + 12) nên ucln(48, 18) = ucln(18, 12). Tương tự như vậy, ucln(18, 12) = ucln(12, 6) = 6.
Hàm ucln(a, b) tính ước chung lớn nhất của hai số a, b theo thuật toán Euclid.
ll ucln(ll a, ll b) { // typedef long long ll;
// return (b == 0) ? a : ucln(b, a % b);
if(b == 0) return a;
return ucln(b, a%b);
}
Hàm __gcd(a, b) trong C++ trả về ucln của hai số a, b.
Bội chung nhỏ nhất
Bội chung nhỏ nhất của hai hay nhiều số nguyên là phần tử nguyên dương nhỏ nhất trong tập các bội chung của các số đó.
Ta kí hiệu [a, b, c,...] hoặc bcnn(a, b, c,...) hoặc lcm(a, b, c,...) thay cho việc gọi bội chung nhỏ nhất của các số a, b, c,... ("least common multiple − lcm" là cụm từ tiếng anh nghĩa là bội chung nhỏ nhất). Ví dụ: [15, 25] = 75; [8, 18, 30] = 360.
Xác định bội chung nhỏ nhất bằng cách: bcnn(a,b) = a.b/ucln(a,b). Để tránh tràn số, ta biến đổi thành bcnn(a,b) = a/ucln(a,b).b.
ll bcnn(ll a, ll b) {
return a/ucln(a, b)*b; // chia trước rồi mới nhân
}
Liên hệ giữa gcd(a, b) và lcm(a, b)
Công thức: a.b = gcd(a, b).lcm(a, b) thể hiện liên hệ giữa gcd(a, b) và lcm(a, b). Từ đây, ta có thể dễ dàng tìm được đại lượng còn lại:
lcm(a, b) = a.b/gcd(a,b) và gcd(a, b) = a.b/lcm(a, b).
Luyện tập
Bài 1. Chia kẹo
Cô giáo có n viên kẹo và muốn chia đều cho một số bạn sao cho không thừa viên nào. Hãy liệt kê tất cả số bạn có thể chia, theo thứ tự tăng dần.
| Đầu vào | Một số nguyên n (1 ≤ n ≤106) | |
|---|---|---|
| Đầu ra | Kết quả bài toán | |
| Test | Input | Output |
| 12 | 1 2 3 4 6 12 | |
Bài 2. Đếm ước số thần tốc
Gấu được giao đếm số ước của những con số rất lớn. Là một người thạo lập trình, Gấu liền viết chương trình đếm số ước của n thật nhanh.
| Đầu vào | Một số nguyên n (1 ≤ n ≤109) | |
|---|---|---|
| Đầu ra | Số lượng ước của n. | |
| Test | Input | Output |
| 36 | 9 | |
Bài 3. Đếm bội số trong đoạn
Hãy đếm xem trong đoạn từ a đến b có bao nhiêu số chia hết cho k.
| Đầu vào | Ba số nguyên a, b, k (1 ≤ a ≤ b ≤ 109; 1 ≤ k ≤ 109) | |
|---|---|---|
| Đầu ra | Số lượng số chia hết cho k trong đoạn từ a đến b | |
| Test | Input | Output |
| 5 20 3 | 5 | |
Bài 4. Phân số tối giản
Nam phải làm bài tập rút gọn phân số a/b về dạng tối giản nhất c/d. Hãy giúp Nam viết một chương trình máy tính kiểm tra bài làm của mình nhé!
| Đầu vào | Hai số nguyên a, b (1 ≤ a, b ≤ 109) | |
|---|---|---|
| Đầu ra | Hai số c và d của phân số tối giản c/d cách nhau một khoảng trắng. | |
| Test | Input | Output |
| 12 18 | 2 3 | |
- Ghi chú: để rút gọn phân số a/b, ta chia a và b cho ucln(a, b).
Bài 5. Số hoàn hảo
Một số nguyên dương được gọi là "Số hoàn hảo" nếu tổng tất cả các ước số nhỏ hơn nó bằng chính nó (Ví dụ: số 6 có các ước nhỏ hơn nó là 1, 2, 3 và 1+2+3 = 6). Kiểm tra xem n có phải là số hoàn hảo hay không!
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 1012) | |
|---|---|---|
| Đầu ra | In ra YES nếu n là số hoàn hảo, ngược lại in ra NO. | |
| Test | Input | Output |
| 28 | YES | |
| 10 | NO | |
Bài 6. Nguyên tố cùng nhau
Hai bạn học sinh mang số áo a và b được xếp cùng một đội chơi nếu hai số áo của các bạn là hai số nguyên tố cùng nhau (gcd(a, b) = 1). Em hãy kiểm tra xem hai bạn có được vào cùng một đội không nhé.
| Đầu vào | Hai số nguyên a, b (1 ≤ a, b ≤ 1012) | |
|---|---|---|
| Đầu ra | In ra YES nếu hai bạn có thể xếp cùng đội, ngược lại in ra NO. | |
| Test | Input | Output |
| 8 15 | YES | |
| 14 21 | NO | |
Bài 7. Xếp gạch vuông
Nền nhà hình chữ nhật có kích thước a.b. Bác thợ muốn lát bằng các viên gạch hình vuông, cạnh dài nhất có thể, sao cho vừa khít và không phải cắt gạch. Hãy cho biết cạnh viên gạch và số viên gạch cần dùng.
| Đầu vào | Hai số nguyên a, b (1 ≤ a, b ≤ 109) | |
|---|---|---|
| Đầu ra | Hai số cách nhau một dấu cách: cạnh viên gạch và số viên gạch | |
| Test | Input | Output |
| 48 18 | 6 24 | |
Bài 8. Hai ngọn đèn nhấp nháy
Đèn A cứ a giây nháy một lần, đèn B cứ b giây nháy một lần. Cả hai cùng nháy ở giây số 0. Hỏi sau ít nhất bao nhiêu giây (lớn hơn 0) thì hai đèn lại cùng nháy một lúc?
| Đầu vào | Hai số nguyên a, b (1 ≤ a, b ≤ 109) | |
|---|---|---|
| Đầu ra | In ra số giây ít nhất để hai đèn lại cùng nháy. | |
| Test | Input | Output |
| 12 18 | 36 | |
| 1000000000 999999999 | 999999999000000000 | |
Bài tập tự luyện
Bài 1. ƯCLN và BCNN của dãy số
Cho một dãy gồm n số. Hãy tìm ƯCLN và BCNN của tất cả các số trong dãy.
| Đầu vào | Dòng 1: số nguyên n; Dòng 2: n số nguyên dương a[i]. | |
|---|---|---|
| Giới hạn | 1 ≤ n ≤ 1000; 1 ≤ a[i] ≤ 109; đảm bảo BCNN không vượt quá 1018. | |
| Đầu ra | Hai số cách nhau một dấu cách: ƯCLN và BCNN của cả dãy. | |
| Test | Input | Output |
| 4 12 18 24 30 | 6 360 | |
Bài 2. Những người bạn thân của n
Hai số được gọi là "bạn thân" nếu chúng nguyên tố cùng nhau. Trong các số từ 1 đến n, có bao nhiêu số là bạn thân của n?
| Đầu vào | Số nguyên n (1 ≤ n ≤ 105) | |
|---|---|---|
| Đầu ra | Kết quả bài toán | |
| Test | Input | Output |
| 10 | 4 | |
| 7 | 6 | |
Bài 3. Đếm ước chung
Cho hai số a và b. Hãy đếm xem hai số có bao nhiêu ước chung? Liệt kê tất cả ước chung của a và b theo thứ tự tăng dần.
| Đầu vào | Hai số nguyên a, b (1 ≤ a, b ≤ 109) | |
|---|---|---|
| Đầu ra | Dòng 1: Số lượng ước chung của a và b. Dòng 2: các ước chung theo thứ tự tăng dần, cách nhau dấu cách | |
| Test | Input | Output |
| 12 18 | 4 1 2 3 6 | |
Bài 4. Số nhỏ nhất chia hết cho 1 đến n
Tìm số nguyên dương nhỏ nhất chia hết cho tất cả các số từ 1 đến n.
| Đầu vào | Số nguyên n (1 ≤ n ≤ 40) | |
|---|---|---|
| Đầu ra | Số nhỏ nhất chia hết cho mọi số từ 1 đến n | |
| Test | Input | Output |
| 10 | 2520 | |
| 20 | 232792560 | |
Bài 5. Chia hết cho a hoặc b
Trong đoạn từ l đến r có bao nhiêu số chia hết cho a hoặc chia hết cho b?
| Đầu vào | Bốn số nguyên l, r, a, b. (1 ≤ l ≤ r ≤ 109; 1 ≤ a, b ≤ 109) | |
|---|---|---|
| Đầu ra | Số lượng số trong đoạn [l, r] chia hết cho a hoặc b | |
| Test | Input | Output |
| 1 30 3 5 | 14 | |
| 10 20 2 4 | 6 | |
Bài 6. Tìm hai số khi biết ƯCLN và BCNN
Biết ƯCLN của hai số nguyên dương a và b (a ≤ b) là x, BCNN(a, b) là y. Hãy tìm hai số a, b có hiệu b − a nhỏ nhất.
| Đầu vào | Hai số x, y (1 ≤ x ≤ y ≤ 109, y chia hết cho x) | |
|---|---|---|
| Đầu ra | Hai số a và b, cách nhau một dấu cách thoả mãn yêu cầu bài toán | |
| Test | Input | Output |
| 3 36 | 9 12 | |
| 2 12 | 4 6 | |
Bài 7. Bí mật của những chiếc bóng đèn
Dọc hành lang trường có n chiếc bóng đèn đánh số từ 1 đến n, ban đầu tất cả đều đang tắt. Có n bạn học sinh đi qua hành lang: bạn thứ 1 bấm công tắc của tất cả các đèn là bội của 1; bạn thứ 2 bấm công tắc của tất cả các đèn là bội của 2;... cứ như vậy bạn thứ k sẽ bấm công tắc của các đèn là bội của k. Cuối cùng, đèn nào được bấm một số lẻ lần sẽ sáng. Hãy in ra số hiệu của các đèn còn sáng nhé!
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 106) | |
|---|---|---|
| Đầu ra | Danh sách các số hiệu đèn còn sáng theo thứ tự tăng dần, cách nhau một khoảng trắng | |
| Test | Input | Output |
| 20 | 1 4 9 16 | |
Bài 8. Cặp đôi nguyên tố cùng nhau
Cho một mảng gồm n số nguyên dương. Hãy đếm xem có bao nhiêu cặp chỉ số (i, j) thỏa mãn 0 ≤ i < j < n sao cho a[i] và a[j] là hai số nguyên tố cùng nhau.
| Đầu vào | Dòng 1: Số nguyên dương n (2 ≤ n ≤ 1000). Dòng 2: n số nguyên dương (1 ≤ a[i] ≤ 109) | |
|---|---|---|
| Đầu ra | Số lượng cặp số nguyên tố cùng nhau tìm được | |
| Test | Input | Output |
| 5 2 4 8 3 6 | 3 | |