Giao diện tối
🏆 CP.04: Số Học & Toán Học Cốt Lõi Cho Chuyên Tin
> Toán học - Linh hồn của Chuyên Tin: Hầu hết các đề thi vào lớp 10 Chuyên Tin và kỳ thi Học sinh Giỏi đều dành ít nhất 1 đến 2 bài cho mảng Số Học (Number Theory): số nguyên tố, ước số, phép toán đồng dư và tổ hợp. Nắm chắc phần này giúp bạn giành trọn 40% điểm của đề thi!
1. Số Học Đồng Dư (Modular Arithmetic) Chuẩn Mực
Khi kết quả bài toán quá lớn, đề bài thường yêu cầu: "Hãy in ra kết quả sau khi chia lấy dư cho $10^9 + 7$".
4 Quy Tắc Bất Di Bất Dịch:
- Phép cộng: $(A + B) \pmod M = ((A \pmod M) + (B \pmod M)) \pmod M$
- Phép nhân: $(A \times B) \pmod M = ((A \pmod M) \times (B \pmod M)) \pmod M$
- Phép trừ (Cực kỳ dễ ăn bẫy số âm!):cpp
// ❌ SAI LẦM: (A - B) % MOD có thể ra số âm trong C++! // ✅ CHUẨN XÁC: Luôn cộng thêm MOD trước khi chia dư: int ans = ((A % MOD) - (B % MOD) + MOD) % MOD; - Phép chia: KHÔNG ĐƯỢC PHÉP chia trực tiếp $((A \pmod M) / (B \pmod M)) \pmod M$! Phải dùng Nghịch đảo Modulo (Modular Inverse)!
2. Lũy Thừa Nhị Phân (Binary Exponentiation) $O(\log B)$
Tính $A^B \pmod M$ với $B$ lên tới $10^{18}$ chỉ trong khoảng 60 phép tính:
cpp
#include <iostream>
using namespace std;
using ll = long long;
// Hàm tính (base^exp) % mod trong O(log exp)
ll power_mod(ll base, ll exp, ll mod) {
ll res = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) { // Nếu bit cuối là 1
res = (__int128_t)res * base % mod; // Dùng __int128_t chống tràn nếu mod lớn
}
base = (__int128_t)base * base % mod;
exp /= 2;
}
return res;
}
int main() {
cout << "2^100 % (1e9+7) = " << power_mod(2, 100, 1e9 + 7) << '\n';
return 0;
}3. Sàng Số Nguyên Tố Eratosthenes Siêu Nhanh
Kiểm tra số nguyên tố cho toàn bộ các số từ $1$ đến $N$ ($N \le 10^7$) trong thời gian $O(N \log \log N)$:
cpp
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 1e7 + 5;
// Dùng vector<bool> được C++ tối ưu hóa từng bit (1 bit/phần tử) tiết kiệm 8 lần RAM!
vector<bool> is_prime(MAXN, true);
void sieve(int n) {
is_prime[0] = is_prime[1] = false;
for (int p = 2; p * p <= n; ++p) {
if (is_prime[p]) {
// Đánh dấu các bội số của p bắt đầu từ p*p
for (int i = p * p; i <= n; i += p) {
is_prime[i] = false;
}
}
}
}
int main() {
int n = 1000000;
sieve(n);
cout << "So 999983 co nguyen to khong? " << (is_prime[999983] ? "Co" : "Khong") << '\n';
return 0;
}4. Nghịch Đảo Modulo & Định Lý Fermat Nhỏ
> Định lý Fermat Nhỏ: Nếu $M$ là một số nguyên tố và $B$ không chia hết cho $M$, thì: > $$B^{M-1} \equiv 1 \pmod M \implies B \cdot B^{M-2} \equiv 1 \pmod M$$ > Do đó, nghịch đảo modulo của $B$ theo modulo $M$ chính là: > $$B^{-1} \equiv B^{M-2} \pmod M$$
Ứng dụng tính phép chia dư:
$$\frac{A}{B} \pmod M = (A \times B^{M-2}) \pmod M$$
cpp
ll mod_inverse(ll b, ll mod) {
return power_mod(b, mod - 2, mod);
}
ll divide_mod(ll a, ll b, ll mod) {
return (a % mod * mod_inverse(b, mod)) % mod;
}5. Tính Tổ Hợp Chập $K$ Của $N$ ($nCk \pmod M$) Trong $O(1)$
Bài toán đếm số cách chọn trong đề thi thường có $N, K \le 10^6$ và có nhiều truy vấn:
cpp
#include <vector>
#include <iostream>
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 5;
const ll MOD = 1e9 + 7;
ll fact[MAXN]; // fact[i] = i! % MOD
ll inv_fact[MAXN];// inv_fact[i] = (i!)^(-1) % MOD
ll power_mod(ll base, ll exp) {
ll res = 1;
base %= MOD;
while (exp > 0) {
if (exp & 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return res;
}
// Tiền xử lý mảng giai thừa trong O(N)
void precompute(int n) {
fact[0] = 1;
inv_fact[0] = 1;
for (int i = 1; i <= n; ++i) {
fact[i] = (fact[i - 1] * i) % MOD;
}
// Nghịch đảo của n!
inv_fact[n] = power_mod(fact[n], MOD - 2);
for (int i = n - 1; i >= 1; --i) {
inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
}
}
// Trả về nCk % MOD chỉ trong O(1)!
ll nCr(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
}
int main() {
precompute(1000000);
cout << "So cach chon 3 hoc sinh tu 10 hoc sinh: " << nCr(10, 3) << '\n'; // 120
return 0;
}