cpp-248Bước 1Cơ bản
Chữ số lớn nhất của một số
Tách chữ số bằng % 10 và / 10 là kỹ thuật cơ bản cho mọi bài số học: kiểm tra đối xứng số, tính tổng chữ số, đếm chữ số. Bài này luyện tìm cực đại trên các chữ số.
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Số học, Số nguyên tố & Giải thuật toán học trong C++
Toán học là nền móng của thuật toán. Nắm chắc các giải thuật số học kinh điển để giải các bài toán số lớn, chia dư và đếm tổ hợp nhanh chóng.
27
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
7
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
12
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
8
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
Kiểm tra nguyên tố
Tối ưu hóa kiểm tra số nguyên tố đến căn bậc hai sqrt(N).
Bước 2
Sàng Eratosthenes
Lọc tất cả số nguyên tố nhỏ hơn N và tìm ước số nguyên tố nhỏ nhất/lớn nhất.
Bước 3
Ước chung lớn nhất (GCD)
Thuật toán Euclid tính GCD/LCM và giải phương trình đồng dư tuyến tính.
Bước 4
Lũy thừa nhanh Modulo
Tính (A^B) % MOD trong thời gian O(log B) và định lý Fermat nhỏ.
Lỗi thường gặp & Cách phòng tránh
•
Quên lấy dư modulo ở từng bước tính tích dẫn đến tràn số trước khi kịp chia dư.
•
Sàng Eratosthenes chạy quá kích thước bộ nhớ nếu mảng tĩnh vượt quá 10^7 phần tử.
Danh sách bài tập thực hành (27 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Cơ bản 7 bài
Khởi động
Nhập xuất, biến, rẽ nhánh và các bước suy luận đơn giản.
cpp-210Bước 2Cơ bản
Ước chung lớn nhất bằng thuật toán Euclid
Ước chung lớn nhất dùng để rút gọn phân số và đồng bộ chu kỳ. Cách duyệt từng ước tốn O(min(a,b)), còn thuật toán Euclid chỉ mất O(log min(a,b)) nhờ hệ thức gcd(a,b) = gcd(b,…
cpp-211Bước 3Cơ bản
Bội chung nhỏ nhất của hai số
Bội chung nhỏ nhất dùng để quy đồng mẫu số và đồng bộ chu kỳ tác vụ. Duyệt bội tốn O(lcm), trong khi hệ thức lcm(a,b) = |a · b| / gcd(a,b) chỉ mất O(log…
cpp-213Bước 4Cơ bản
Kiểm tra số nguyên tố
Kiểm tra nguyên tố là bước mở đầu của mật mã và sàng số. Thử chia mọi số từ 2 tới n-1 tốn O(n); chỉ cần tới √(n) vì nếu n = u × v thì một thừa số không vượt quá √(n).
Làm quen
Vòng lặp, mảng một chiều, chuỗi và hàm ở mức cơ bản.
cpp-215Bước 5Cơ bản
Đếm số ước của một số
Số lượng ước quyết định nhiều tính chất số học: số nguyên tố có đúng hai ước, số chính phương có số ước lẻ. Duyệt tới √(n) và cộng theo từng cặp ước nhanh hơn nhiều so với duyệ…
cpp-216Bước 6Cơ bản
Kiểm tra số chính phương
Số chính phương bằng bình phương của một số nguyên. Trong C++, sqrt trả về số thực nên phải hiệu chỉnh kết quả để tránh sai số khi n lớn.
cpp-124Bước 7Cơ bản
Đếm Số Ước và Tính Tổng Các Ước Của Số Nguyên
Cho số nguyên dương N. Hãy tính:
Trung bình 12 bài
Vận dụng
Dùng một kỹ thuật quen thuộc: sắp xếp, tìm kiếm, đếm, ngăn xếp.
cpp-123Bước 1Trung bình
Ước Chung Lớn Nhất & Định Lý Bézout (Extended Euclidean Algorithm)
Cho hai số nguyên dương A và B. Theo định lý Bézout, luôn tồn tại hai số nguyên x và y sao cho:
cpp-004Bước 2Trung bình
Ước chung lớn nhất và bội chung nhỏ nhất số lớn
Hệ thống mạng nơ-ron phân tán của AI Empire Academy cần đồng bộ hóa chu kỳ cập nhật trọng số giữa hai cụm GPU độc lập. Cụm thứ nhất phát tín hiệu sau mỗi A nano-giây, cụm thứ hai p…
cpp-130Bước 3Trung bình
Tìm Phần Tử Đơn Nhất Bằng Phép XOR (Single Number)
Cho một mảng gồm N số nguyên (N luôn là số lẻ). Biết rằng trong mảng có đúng một số nguyên xuất hiện đúng 1 lần duy nhất, còn mọi số nguyên khác đều xuất hiện đúng 2 lần.
cpp-125Bước 4Trung bình
Thao Tác Bit Cơ Bản (Bit Manipulation Essentials)
Cho một số nguyên không âm 64-bit X và một chỉ số bit K (0 ≤ K ≤ 62, đánh số từ 0 từ phải sang trái).
cpp-247Bước 5Trung bình
Đếm số bit 1 trong biểu diễn nhị phân
Đếm bit 1 là thao tác cơ bản của lập trình hệ thống: kiểm tra cờ trạng thái, nén dữ liệu và tối ưu bộ nhớ. Phép n & 1 lấy bit thấp nhất và n >>= 1 dịch sang phải là đủ để duyệt toà…
cpp-122Bước 6Trung bình
Lũy Thừa Nhị Phân Nhanh Modulo (Fast Modular Exponentiation)
Cho Q truy vấn, mỗi truy vấn gồm ba số nguyên A, B, M. Hãy tính:
Kết hợp kỹ thuật
Phối hợp hai kỹ thuật trong cùng một lời giải.
cpp-214Bước 7Trung bình
Đếm số nguyên tố không vượt quá N
Sàng Eratosthenes đánh dấu bội số của từng số nguyên tố và đếm được cả khoảng trong O(N log log N), nhanh hơn hẳn việc kiểm tra từng số.
cpp-072Bước 8Trung bình
Thuật toán Euclid mở rộng và Phương trình đồng dư Bézout
Cho 3 số nguyên dương a, b, c. Tìm cặp số nguyên (x, y) thỏa mãn:
cpp-121Bước 9Trung bình
Sàng Số Nguyên Tố Trên Đoạn [L, R] (Segmented Sieve)
Cho hai số nguyên dương L và R (1 ≤ L ≤ R ≤ 1012, R - L ≤ 106).
cpp-199Bước 10Trung bình
Sàng tuyến tính O(N): Tính đồng thời Phi Euler và Mobius
Cho số nguyên dương N.
cpp-024Bước 11Trung bình
Lũy thừa nhị phân nhanh và Sàng số nguyên tố Eratosthenes
Hệ thống mã hóa trọng số mô hình AI của AI Empire Academy yêu cầu xử lý hai phép toán số học nền tảng:
cpp-033Bước 12Trung bình
Tính tổ hợp nCr modulo 10^9+7 bằng Định lý Fermat nhỏ
Hệ thống Gateway của AI Empire Academy cần xử lý Q truy vấn thống kê tổ hợp. Mỗi truy vấn gồm hai số nguyên N và K (0 ≤ K ≤ N ≤ 106). Hãy tính giá trị C(N, K) mod 109+7.
Nâng cao 8 bài
Thử thách
Thuật toán chuyên sâu: quy hoạch động, đồ thị, cây.
cpp-074Bước 1Nâng cao
Kiểm tra số nguyên tố xác suất Miller-Rabin cho số lớn 10^18
Cho T số nguyên dương N1, N2, …, NT. Với mỗi số Ni, hãy kiểm tra xem số đó có phải là số nguyên tố hay không.
cpp-076Bước 2Nâng cao
Logarithm rời rạc: Thuật toán Baby-step Giant-step O(sqrt(M))
Cho 3 số nguyên dương A, B, M với M là số nguyên tố và gcd(A, M) = 1. Hãy tìm số nguyên không âm nhỏ nhất x thỏa mãn:
cpp-198Bước 3Nâng cao
Thuật toán Tonelli-Shanks: Khai căn bậc hai modulo số nguyên tố
Cho một số nguyên N và một số nguyên tố lẻ P.
cpp-075Bước 4Nâng cao
Phân tích thừa số nguyên tố: Thuật toán Pollard's Rho O(N^(1/4))
Cho một số nguyên dương N (2 ≤ N ≤ 1018). Hãy tìm tất cả các thừa số nguyên tố của N và in ra theo thứ tự tăng dần (nếu một thừa số xuất hiện nhiều lần thì in tương ứng bấy…
Chuyên sâu
Cấu trúc dữ liệu nâng cao và nhiều bước chứng minh.
cpp-197Bước 5Nâng cao
Extended Baby-Step Giant-Step: Logarithm rời rạc tổng quát
Cho ba số nguyên dương A, B, M.
cpp-073Bước 6Nâng cao
Định lý số dư Trung Hoa (Chinese Remainder Theorem - CRT)
x ≡ ri mod mi (i = 1, …, K)
cpp-200Bước 7Nâng cao
Sàng Du Feng / Min_25: Tính tổng hàm Mobius dưới tuyến tính O(N^(2/3))
Cho số nguyên dương N. Hàm Mertens M(N) là tổng tiền tố của hàm Mobius:
cpp-077Bước 8Nâng cao
Lý thuyết trò chơi: Định lý Sprague-Grundy và Trò chơi Nim
G(u) = mex{G(v) | u → v}