Ước và bội
Rất nhiều bài thi học sinh giỏi hỏi về ước: đếm ước, tính tổng ước, tìm số hoàn hảo, chia nhóm đều nhau… Bài này giúp các bạn làm những việc đó nhanh hơn hàng triệu lần so với cách thử từng số, chỉ nhờ một nhận xét nhỏ: các ước luôn đi theo cặp.
Các bạn nên học trước bài Phép chia có dư và chia hết.
Ước và bội là gì?
Phần tiêu đề “Ước và bội là gì?”12 chia hết cho 3, ta nói:
- 3 là ước của 12 (12 chia hết cho 3, ký hiệu 3 | 12).
- 12 là bội của 3.
Trong code, “d là ước của n” chính là n % d == 0.
Các ước của 12 là 1, 2, 3, 4, 6, 12. Các bội của 3 là 0, 3, 6, 9, 12, … (vô số bội). Số 1 là ước của mọi số, và mọi số đều là ước của chính nó.
Liệt kê ước: cách thử từng số
Phần tiêu đề “Liệt kê ước: cách thử từng số”Cách dễ nghĩ nhất là thử mọi số từ 1 đến n:
n = 36for d in range(1, n + 1): if n % d == 0: print(d, end=" ") # 1 2 3 4 6 9 12 18 36Cách này đúng nhưng chậm: với n = 1012, máy phải thử 1012 số, ước lượng mất khoảng 3 tiếng.
Ước luôn đi theo cặp
Phần tiêu đề “Ước luôn đi theo cặp”Nhìn các ước của 36 theo từng cặp có tích bằng 36:
| Ước nhỏ | Ước lớn | Tích |
|---|---|---|
| 1 | 36 | 36 |
| 2 | 18 | 36 |
| 3 | 12 | 36 |
| 4 | 9 | 36 |
| 6 | 6 | 36 |
Mỗi khi tìm được một ước d, ta có ngay ước thứ hai là n / d. Và trong mỗi cặp, ước nhỏ không vượt quá √n (với 36 là 6): nếu cả hai số trong cặp đều lớn hơn 6 thì tích đã lớn hơn 6 × 6 = 36 rồi.
Vậy chỉ cần thử d từ 1 đến √n, mỗi lần gặp ước thì lấy luôn cả cặp:
| n | Thử từng số | Thử đến √n |
|---|---|---|
| 106 | 106 lần | 103 lần |
| 1012 | 1012 lần (ước lượng khoảng 3 tiếng) | 106 lần (rất nhanh) |
n = int(input())dem = 0d = 1while d * d <= n: # thử d đến căn bậc hai của n if n % d == 0: dem += 1 # ước nhỏ d if d != n // d: dem += 1 # ước lớn n // d (khác d) d += 1print(dem) # n = 36 in ra 9#include <iostream>using namespace std;
int main() { long long n; cin >> n; int dem = 0; for (long long d = 1; d * d <= n; d++) { // thử d đến căn bậc hai của n if (n % d == 0) { dem++; // ước nhỏ d if (d != n / d) dem++; // ước lớn n / d (khác d) } } cout << dem << endl; // n = 36 in ra 9 return 0;}Lưu ý:
- Khi n là số chính phương (36 = 6 × 6), cặp (6, 6) chỉ là một ước. Nếu
quên kiểm tra
d != n // d, chương trình sẽ đếm 6 hai lần. - Viết điều kiện
d * d <= n, không viếtd <= sqrt(n). Hàmsqrttính bằng số thực nên có thể sai một chút với số lớn (ví dụ trả về 999999.9999 thay vì 1000000), làm thiếu mất một ước. - Trong C++,
dphải làlong long: khi n gần 1012 thìd * dvượt quá giới hạn củaint.
Liệt kê ước theo thứ tự tăng dần
Phần tiêu đề “Liệt kê ước theo thứ tự tăng dần”Ước nhỏ tìm được theo thứ tự tăng dần (1, 2, 3, 4, 6), còn ước lớn theo thứ tự giảm dần (36, 18, 12, 9). Lưu hai danh sách riêng rồi ghép: ước nhỏ, sau đó ước lớn đảo ngược.
n = 36nho, lon = [], []d = 1while d * d <= n: if n % d == 0: nho.append(d) if d != n // d: lon.append(n // d) d += 1print(*(nho + lon[::-1])) # 1 2 3 4 6 9 12 18 36#include <iostream>#include <vector>using namespace std;
int main() { long long n = 36; vector<long long> nho, lon; for (long long d = 1; d * d <= n; d++) { if (n % d == 0) { nho.push_back(d); if (d != n / d) lon.push_back(n / d); } } for (long long x : nho) cout << x << " "; for (int i = (int)lon.size() - 1; i >= 0; i--) cout << lon[i] << " "; cout << endl; // 1 2 3 4 6 9 12 18 36 return 0;}Cùng cách đó, muốn tính tổng các ước thì thay việc đếm bằng cộng d và n / d.
Số hoàn hảo
Phần tiêu đề “Số hoàn hảo”Số hoàn hảo là số bằng tổng các ước nhỏ hơn nó. Ví dụ 6 = 1 + 2 + 3 và 28 = 1 + 2 + 4 + 7 + 14. Đây là dạng bài rất hay gặp: tính tổng các ước bằng cách duyệt đến √n, rồi trừ đi chính n.
Các bội của k là 0, k, 2k, 3k, … Hai câu hỏi hay gặp:
- Bội lớn nhất không vượt quá n: lấy phần nguyên rồi nhân lại,
n // k * k. Ví dụ n = 2026, k = 7: 2026 // 7 = 289, 289 × 7 = 2023. - Bội nhỏ nhất không nhỏ hơn n: làm tròn lên rồi nhân lại,
(n + k - 1) // k * k. Ví dụ trên được 2030.
Đếm số bội của k trong một đoạn thì dùng công thức b // k - (a - 1) // k đã học
ở bài Phép chia có dư và chia hết.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 21 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Liệt kê và đếm ước
Phần tiêu đề “Nhóm 1. Liệt kê và đếm ước”Bài 1. Liệt kê ước
Phần tiêu đề “Bài 1. Liệt kê ước”Nhập số nguyên dương n (n ≤ 1012). In ra các ước của n theo thứ tự tăng dần, cách nhau một dấu cách.
Ví dụ: nhập 12 thì in ra 1 2 3 4 6 12.
Kiểm tra: nhập 36.
Bài 2. Đếm ước
Phần tiêu đề “Bài 2. Đếm ước”Nhập số nguyên dương n (n ≤ 1012). In ra số ước của n.
Ví dụ: nhập 36 thì in ra 9.
Kiểm tra: nhập 1000000000000.
Bài 3. Tổng các ước
Phần tiêu đề “Bài 3. Tổng các ước”Nhập số nguyên dương n (n ≤ 1012). In ra tổng tất cả các ước của n (kể cả 1 và n).
Ví dụ: nhập 12 thì in ra 28.
Kiểm tra: nhập 360.
Bài 4. Ước lớn nhất nhỏ hơn n
Phần tiêu đề “Bài 4. Ước lớn nhất nhỏ hơn n”Nhập số nguyên n (2 ≤ n ≤ 1012). In ra ước lớn nhất của n mà nhỏ hơn n.
Ví dụ: nhập 12 thì in ra 6.
Kiểm tra: nhập 1001.
Bài 5. Đếm ước lẻ
Phần tiêu đề “Bài 5. Đếm ước lẻ”Nhập số nguyên dương n (n ≤ 1012). In ra số ước lẻ của n.
Ví dụ: nhập 12 thì in ra 2.
Kiểm tra: nhập 360.
Bài 6. Số hoàn hảo
Phần tiêu đề “Bài 6. Số hoàn hảo”Số hoàn hảo là số bằng tổng các ước nhỏ hơn nó, ví dụ 6 = 1 + 2 + 3. Nhập số nguyên dương n (n ≤ 1012), in ra YES nếu n là số hoàn hảo, ngược lại in ra NO.
Ví dụ: nhập 28 thì in ra YES.
Kiểm tra: nhập 8128.
Bài 7. Liệt kê số hoàn hảo
Phần tiêu đề “Bài 7. Liệt kê số hoàn hảo”Nhập số nguyên dương n (n ≤ 105). In ra các số hoàn hảo không vượt quá n, theo thứ tự tăng dần, cách nhau một dấu cách. Nếu không có số nào thì in ra 0.
Ví dụ: nhập 100 thì in ra 6 28.
Kiểm tra: nhập 10000.
Nhóm 2. Bội
Phần tiêu đề “Nhóm 2. Bội”Bài 8. Bội nhỏ nhất không nhỏ hơn n
Phần tiêu đề “Bài 8. Bội nhỏ nhất không nhỏ hơn n”Nhập hai số nguyên dương n, k (n, k ≤ 1012). In ra bội nhỏ nhất của k mà lớn hơn hoặc bằng n.
Ví dụ: nhập 20 7 thì in ra 21.
Kiểm tra: nhập 2026 7.
Bài 9. Bội lớn nhất không vượt quá n
Phần tiêu đề “Bài 9. Bội lớn nhất không vượt quá n”Nhập hai số nguyên dương n, k (k ≤ n ≤ 1018). In ra bội lớn nhất của k mà nhỏ hơn hoặc bằng n.
Ví dụ: nhập 20 7 thì in ra 14.
Kiểm tra: nhập 2026 7.
Bài 10. Bội gần nhất
Phần tiêu đề “Bài 10. Bội gần nhất”Nhập hai số nguyên dương n, k (k ≤ n ≤ 1018). In ra bội của k gần n nhất. Nếu có hai bội cách n bằng nhau thì in ra bội nhỏ hơn.
Ví dụ: nhập 20 8 thì in ra 16.
Kiểm tra: nhập 2026 8.
Bài 11. Bội của a nhưng không là bội của b
Phần tiêu đề “Bài 11. Bội của a nhưng không là bội của b”Nhập ba số nguyên dương n, a, b (n ≤ 1018, b là bội của a). Đếm xem từ 1 đến n có bao nhiêu số chia hết cho a nhưng không chia hết cho b.
Ví dụ: nhập 20 2 4 thì in ra 5.
Kiểm tra: nhập 1000 3 9.
Nhóm 3. Ước trong bài toán thực tế
Phần tiêu đề “Nhóm 3. Ước trong bài toán thực tế”Bài 12. Bài toán bóng đèn
Phần tiêu đề “Bài 12. Bài toán bóng đèn”Có n bóng đèn đánh số từ 1 đến n, ban đầu đều tắt. Có n lượt bấm: ở lượt thứ i, người ta bấm công tắc của mọi bóng có số thứ tự chia hết cho i (bóng đang tắt thì sáng, đang sáng thì tắt). Nhập n (n ≤ 1018), in ra số bóng đèn sáng sau n lượt.
Ví dụ: nhập 10 thì in ra 3.
Kiểm tra: nhập 2026.
Bài 13. Chia nhóm đều nhau
Phần tiêu đề “Bài 13. Chia nhóm đều nhau”Lớp có n học sinh (n ≤ 1012). Cô muốn chia lớp thành các nhóm có số người bằng nhau, mỗi nhóm ít nhất 2 người và có ít nhất 2 nhóm. In ra số cách chia.
Ví dụ: nhập 12 thì in ra 4.
Kiểm tra: nhập 36.
Bài 14. Hình chữ nhật chu vi nhỏ nhất
Phần tiêu đề “Bài 14. Hình chữ nhật chu vi nhỏ nhất”Nhập số nguyên dương n (n ≤ 1012). Xét các hình chữ nhật có hai cạnh là số nguyên dương và diện tích đúng bằng n. In ra chu vi nhỏ nhất của các hình chữ nhật đó.
Ví dụ: nhập 12 thì in ra 14.
Kiểm tra: nhập 1000.
Bài 15. Đếm cặp có tích bằng n
Phần tiêu đề “Bài 15. Đếm cặp có tích bằng n”Nhập số nguyên dương n (n ≤ 1012). Đếm số cặp số nguyên dương (a, b) với a ≤ b và a × b = n.
Ví dụ: nhập 12 thì in ra 3.
Kiểm tra: nhập 360.
Bài 16. Ước lẻ lớn nhất
Phần tiêu đề “Bài 16. Ước lẻ lớn nhất”Nhập số nguyên dương n (n ≤ 1018). In ra ước lẻ lớn nhất của n.
Ví dụ: nhập 24 thì in ra 3.
Kiểm tra: nhập 2074624.
Nhóm 4. Ước của nhiều số
Phần tiêu đề “Nhóm 4. Ước của nhiều số”Bài 17. Ước chung của hai số
Phần tiêu đề “Bài 17. Ước chung của hai số”Nhập hai số nguyên dương a, b (a, b ≤ 1012). In ra các ước chung của a và b theo thứ tự tăng dần, cách nhau một dấu cách.
Ví dụ: nhập 12 18 thì in ra 1 2 3 6.
Kiểm tra: nhập 36 48.
Bài 18. Tổng số ước từ 1 đến n
Phần tiêu đề “Bài 18. Tổng số ước từ 1 đến n”Gọi d(x) là số ước của x. Nhập số nguyên dương n (n ≤ 107), in ra d(1) + d(2) + … + d(n).
Ví dụ: nhập 10 thì in ra 27.
Kiểm tra: nhập 1000.
Bài 19. Tổng các tổng ước
Phần tiêu đề “Bài 19. Tổng các tổng ước”Gọi σ(x) là tổng các ước của x. Nhập số nguyên dương n (n ≤ 107), in ra σ(1) + σ(2) + … + σ(n).
Ví dụ: nhập 4 thì in ra 15.
Kiểm tra: nhập 1000.
Bài 20. Số có nhiều ước nhất
Phần tiêu đề “Bài 20. Số có nhiều ước nhất”Nhập số nguyên dương n (n ≤ 106). In ra số trong đoạn từ 1 đến n có nhiều ước nhất và số ước của nó. Nếu có nhiều số cùng nhiều ước nhất thì chọn số nhỏ nhất.
Ví dụ: nhập 10 thì in ra 6 4.
Kiểm tra: nhập 1000.
Bài 21. Đếm số dư thừa
Phần tiêu đề “Bài 21. Đếm số dư thừa”Số dư thừa là số có tổng các ước nhỏ hơn nó lớn hơn chính nó, ví dụ 12 (1 + 2 + 3 + 4 + 6 = 16 > 12). Nhập số nguyên dương n (n ≤ 106), đếm số dư thừa không vượt quá n.
Ví dụ: nhập 20 thì in ra 3.
Kiểm tra: nhập 1000.
© 2026 Bumbii Academy. Toàn bộ nội dung thuộc bản quyền của Bumbii Academy, nghiêm cấm sao chép dưới mọi hình thức khi chưa được cho phép.