Phương pháp phân nhóm theo số chữ số
Dãy số:
Nhóm 1: Có 9 số có 1 chữ số () chữ số.
Nhóm 2: Có 90 số có 2 chữ số () chữ số.
Nhóm 3: Có 900 số có 3 chữ số () chữ số.
Tổng quát: Nhóm có chữ số sẽ có chữ số.
ll len = 1; // Số chữ số của các số trong nhóm hiện tại
ll cnt = 9; // Số lượng số trong nhóm hiện tại (9, 90, 900...)
ll start = 1; // Số bắt đầu của nhóm (1, 10, 100...)
// Bước 1: Xác định xem n nằm trong nhóm có bao nhiêu chữ số
while (n > len * cnt) {
n -= len * cnt;
len++;
cnt *= 10;
start *= 10;
}
// Bước 2: Tìm số cụ thể chứa chữ số thứ n
// (n-1) để chuyển về 0-indexed trong phạm vi nhóm
ll target = start + (n - 1) / len;
// Bước 3: Tìm chữ số cụ thể trong target
string s = to_string(target);
cout << s[(n - 1) % len];Digital Root trong tổng các chữ số
Khái niệm
Digit Sum: Là kết quả của việc cộng tất cả các chữ số của một số tự nhiên lại với nhau.
Digital Root: Là giá trị nhận được khi thực hiện tổng các chữ số liên tiếp nhiều lần cho đến khi chỉ còn lại một chữ số duy nhất (từ 1 9).
Quy tắc: Digital Root của một số chính là số dư của phép chia cho 9, một ngoại lệ là khi phép chia dư 0 thì kết quả là 9.
Công thức tổng quát:
Một số tính chất
Casting Out Nines: Digital Root của một tổng (hoặc tích) bằng tổng (hoặc tích) các Digital Root của các thành phần. (Được dùng để kiểm tra độ chính xác của một phép cộng hoặc phép nhân)
Dấu hiệu chia hết 3 và 9: Một số chia hết cho 3 (hoặc 9) khi và chỉ khi Digital Root của nó chia hết cho 3 (hoặc là 9).
Hiệu số: Hiệu của một số và tổng các chữ số của nó luôn chia hết cho 9.
Tổng các digital sum từ đến :
ll compute(ll n) {
ll q = n / 9;
ll r = n % 9;
return 45 * q + r *(r + 1) / 2;
}Floor/ceil trick
// bit trick
// a ^ b >= 0: cùng dấu
// a ^ b < 0: trái dấu
ll floor_div(ll a, ll b) {
return a / b - ((a % b != 0) & ((a ^ b) < 0)); // làm tròn xuống
}
ll ceil_div(ll a, ll b) {
return a / b + ((a % b != 0) & ((a ^ b) >= 0)); // làm tròn lên
}Kiểm tra có nằm trong hoặc trên cạnh
Cách 1: Dựa trên tổng diện tích (Area Method)
Công thức:
Nếu nằm ngoài, tổng diện tích 3 tam giác con sẽ lớn hơn .
struct Point {
double x, y;
};
double area(Point A, Point B, Point C) { // sử dụng công thức shoelace
return 0.5 * abs(A.x * (B.y - C.y) + B.x * (C.y - A.y) + C.x * (A.y - B.y));
}
inline bool inside_area(Point A, Point B, Point C, Point M) {
double S_ABC = area(A, B, C);
double S_ABM = area(A, B, M);
double S_BCM = area(B, C, M);
double S_CAM = area(C, A, M);
double epsilon = 1e-9;
return abs(S_ABC - (S_ABM + S_BCM + S_CAM)) < epsilon;
}Cách 2: Dựa vào Tích có hướng (Cross Product / Orientation)
Nguyên lý: Điểm nằm trong tam giác khi và chỉ khi nằm cùng phía đối với cả 3 đường thẳng chứa cạnh tam giác. (Xác định hướng nằm của M sử dụng quy tắc bàn tay phải)
Công thức tích có hướng: Với 3 điểm , tích có hướng của và là:
Nếu : nằm bên trái .
Nếu : nằm bên phải .
Nếu : thẳng hàng với .
struct Point {
double x, y;
};
ll cross(Point A, Point B, Point C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline bool inside_area(Point A, Point B, Point C, Point M) {
ll cp1 = cross(A, B, M);
ll cp2 = cross(B, C, M);
ll cp3 = cross(C, A, M);
return ((cp1 >= 0 && cp2 >= 0 && cp3 >= 0) || (cp1 <= 0 && cp2 <= 0 && cp3 <= 0));
}So sánh
Đặc điểm | Cách 1 (Diện tích) | Cách 2 (Tích có hướng) |
|---|---|---|
Độ chính xác | Thấp (do sai số | Tuyệt đối |
Tốc độ | Chậm hơn (phép chia/căn) | Rất nhanh (chỉ nhân/cộng) |
Độ phức tạp | ||
Khuyên dùng | Toán phổ thông, lý thuyết | Lập trình thi đấu |
Số Delannoy
Khái niệm
Số Delannoy, ký hiệu là , đếm số lượng đường đi từ điểm góc đến điểm trên lưới tọa độ Oxy, với quy tắc di chuyển chỉ được phép sử dụng 3 bước đi sau:
Đi lên (North):
Đi sang phải (East):
Đi chéo lên-phải (North-East):
Điều này khác với bài toán đường đi cơ bản (chỉ lên và sang phải - liên quan đến hệ số nhị thức) ở chỗ nó cho phép đi chéo.
Số Delannoy trung tâm (Central Delannoy Numbers): Là trường hợp đặc biệt khi lưới là hình vuông, tức là .
Công thức truy hồi
( là biên)
Độ phức tạp: .
Công thức tổ hợp
Giả sử ta thực hiện bước đi chéo:
Số bước chéo:
Số bước lên:
Số bước lên:
Tổng số bước đi:
Độ phức tạp: .
Ở trên là đi từ , nếu bài toán là thì cần biến đổi
Định lý Dilworth (bài toán lồng nhau, …)
Bản chất
Định lý này áp dụng trên một Tập thứ tự bộ phận (Partially Ordered Set - POSET).
Chuỗi (Chain): Một tập hợp con mà mọi cặp phần tử đều so sánh được với nhau (ví dụ: giống như búp bê Nga lồng vào nhau).
Đối xích (Antichain): Một tập hợp con mà không có cặp phần tử nào so sánh được với nhau (độc lập hoàn toàn).
Phát biểu: Số lượng tối thiểu các Chuỗi cần thiết để phủ kín tập hợp = Kích thước của Đối xích dài nhất (Maximum Antichain).
Một số bài toán kinh điển
1. Dãy số: Cho một dãy số, tìm số lượng tối thiểu các dãy con tăng dần để phủ hết dãy số ban đầu.
2. Hình học (Nested Boxes): Cho các hộp có kích thước . Hộp A lồng được vào B nếu và . Tìm số hộp ít nhất không lồng nhau (Max Antichain) hoặc số chồng hộp ít nhất (Min Chain Cover).
Bảng tổng quát
Quy tắc: “Có dấu BẰNG thì mất, không có dấu BẰNG thì thêm.”
# | Yêu cầu bài toán | Chain | Antichain | Dilworth |
|---|---|---|---|---|
1 | Phủ bằng dãy không giảm | Dãy con giảm dần | ||
2 | Phủ bằng dãy không tăng | Dãy con tăng dần | ||
3 | Phủ bằng dãy tăng nghiêm ngặt | Dãy con không tăng | ||
4 | Phủ bằng dãy giảm nghiêm ngặt | Dãy con không giảm |
Thuật toán Euclid mở rộng
ll extended_euclid(ll a, ll b, ll &x, ll &y) {
if(b == 0) {
x = 1;
y = 0;
return a;
}
ll x1, y1;
ll g = extended_euclid(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return g;
}Diophinate tìm các nghiệm
bool exist_solution(ll a, ll b, ll c, ll &x, ll &y, ll &g){
g = extended_euclid(abs(a), abs(b), x, y);
if(c % g) return 0;
x *= c / g;
y *= c / g;
if(a < 0) x = -x;
if(b < 0) y = -y;
return 1;
}
// x = x0 + b/g
// y = y0 - a/g
ll find_all_solutions(ll a, ll b, ll c, ll minx, ll maxx, ll miny, ll maxy) {
ll x0, y0, g;
if(!exist_solution(a, b, c, x0, y0, g)) return 0;
a /= g; // chuan hoa
b /= g;
// x = x0 + k*b => minx <= x0 + k*b <= maxx
ll kx1, kx2;
if(b > 0) {
kx1 = ceil_div(minx - x0, b);
kx2 = floor_div(maxx - x0, b);
} else {
kx1 = ceil_div(maxx - x0, b);
kx2 = floor_div(minx - x0, b);
}
// y = y0 - k*a => miny <= y0 - k*a <= maxy
// => -miny + y0 >= k*a >= -maxy + y0
ll ky1, ky2;
if(a > 0) {
ky1 = ceil_div(-maxy + y0, a);
ky2 = floor_div(-miny + y0, a);
} else {
ky1 = ceil_div(-miny + y0, a);
ky2 = floor_div(-maxy + y0, a);
}
ll l = max(kx1, ky1);
ll r = min(kx2, ky2);
if(l > r) return 0;
else return r - l + 1;
}Nghịch đảo modulo
TH1: M là số nguyên tố
ll bin_pow(ll a, ll b, ll m) {
ll res = 1;
a = a % m;
while(b) {
if(b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
bin_pow(a, m - 2, m)TH2: M là hợp số (Euclid mở rộng)
ll modinv(ll a, ll m) {
ll x, y;
ll g = extended_euclid(a, m, x, y);
if(g != 1) return -1;
return (x % m + m) % m;
}Phi hàm Euler
Công thức
int phi = primes_pw[i] - primes_pw[i] / primes[i];Sàng phi
int phi[limN];
void init() {
FOR(i, 1, limN) {
phi[i] = i;
}
FOR(i, 2, limN) {
if(phi[i] == i) { // i là số nguyên tố
for(int j = i; j < limN; j += i) {
phi[j] -= phi[j] / i;
}
}
}
}Định lý Thặng dư Trung Hoa CRT
Giả sử bạn có một hệ gồm phương trình đồng dư:
Điều kiện bắt buộc: Các module phải đôi một nguyên tố cùng nhau.
Phương trình này luôn có một nghiệm duy nhất modulo
Ta có:
Vậy nghiệm thõa mãn là:
const int mod = 142857; // 142857 = 3 ^ 3 * 11 * 13 * 17
int n_primes = 4;
int primes[] = {3, 11, 13, 37};
int primes_pw[] = {27, 11, 13, 37};
int rem[n_primes];
void init(){ // tính trước N_i * N_i^(-1)
FOR(i, 0, n_primes) {
int tmp = mod / primes_pw[i]; // N_i
int phi = primes_pw[i] - primes_pw[i] / primes[i]; // phi Euler
// tính N_i^(-1) sử dụng định lý Euler
rem[i] = tmp * bin_pow(tmp, phi - 1, primes_pw[i]) % mod;
}
}
ll CRT(ll n, ll k) {
ll res = 0;
FOR(i, 0, n_primes) {
// a_i ở đây là C(n, k, primes_pw[i]): hàm tính nCk modulo primes_pw[i]
res += C(n, k, primes_pw[i]) * rem[i] % mod;
res %= mod;
}
return res;
}Công thức Legendre
// Hàm đếm số mũ của p trong n! (Công thức Legendre)
ll legendre_(ll n, ll p) {
ll res = 0;
while (n) {
res += n / p;
n /= p;
}
return res;
}Tổ hợp
Tam giác Pascal (Quy hoạch động)
for (int i = 0; i <= n; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}
}Precompute giai thừa
const int mod = 1e9 + 7;
const int limN = 1e6 + 5;
ll fact[limN], inv_fact[limN];
ll bin_pow(ll a, ll b, ll m) {
ll res = 1;
a = a % m;
while(b) {
if(b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
void init() {
fact[0] = 1;
FOR(i, 1, limN) {
fact[i] = fact[i - 1] * i % mod;
}
inv_fact[limN - 1] = bin_pow(fact[limN - 1], mod - 2, mod);
for(int i = limN - 2; i >= 0; i--) {
inv_fact[i] = inv_fact[i + 1] * (i + 1) % mod;
}
}
ll comb(ll n, ll k) {
if(n < k) return 0;
return fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod;
}Lặp gộp chung tử và mẫu
Ta có: và
Base case:
ll res = 1;
FOR(i, 1, k + 1) {
res = res * (n - i + 1) % mod;
res = res * bin_pow(i, mod - 2, mod) % mod;
}
cout << res;Định lý Lucas
Phát biểu
Cho là một số nguyên tố, và thuộc số nguyên không âm, khi đó:
Trong đó:
Là biểu diễn của n và k trên hệ cơ số p.
Công thức đệ quy:
int C(ll n, ll k){...} // hàm tính nCk sử dụng định nghĩa lũy thừa nhị phân
int comb(ll n, ll k){
if (n < k) return 0;
ll res = 1;
while (n > 0 || k > 0){
ll ni = n % mod, ki = k % mod;
if(ki > ni) return 0;
res = res * C(ni, ki) % mod;
n /= mod; k/= mod;
}
return res;
}Hệ quả
chia hết cho số nguyên tố khi và chỉ khi có ít nhất một chữ số của trong biểu diễn cơ số p lớn hơn chữ số tương ứng của n.
Giải thích: thì
là một số lẻ khi và chỉ khi trong biểu diễn nhị phân, bất cứ khi nào bit thứ của là , thì bit thứ của cũng phải là .
Giải thích: Xét trường hợp . Các chữ số trong biểu diễn cơ số 2 là 0 hoặc 1. Tích sẽ không phải là 0 (tức bằng 1) khi và chỉ khi các thừa số . Điều này sẽ xảy ra khi không có trường hợp và và ngược lại. Nói cách khác, nếu thì cũng phải bằng 1. Theo logic bit, ta có thể kiểm tra dễ dàng với phép toán
(n & k) == khoặc(k & n) == k.
Định lý Mở Rộng Lucas (Kết hợp định lý Wilson)
Khi bạn muốn tính tổ hợp chập của :
Nếu là số nguyên tố: Dễ dàng sử dụng Định lý Lucas nêu trên.
Nếu (lũy thừa của số nguyên tố): Trong mẫu số có thể chứa các thừa số . Khi một số chia hết cho thì không có nghịch đảo modulo theo modulo .
Vậy một giải pháp được đề xuất:
Rút toàn bộ thừa số ra khỏi các giai thừa, tính toán với phần còn lại. Vì phần còn lại sẽ nguyên tố cùng nhau với , chúng ta có thể dễ dàng tìm nghịch đảo modulo (modular inverse).
Công thức tổng quát:
Trong đó:
Nếu số mũ của lớn hơn hoặc bằng , tức là:
Khi đó, ta có thể kết luận ngay:
Nhân bù số lượng đã rút ra trở lại, và xử lý dấu (+1/-1).
Khi tính modulo , ta có chia các số thành các chu kỳ (blocks) độ dài . Bởi vậy thay vì kiểm tra -1 hay 1 như công thức của Andrew Granville thì ta có thể sử dụng Định lý Wilson mở rộng:
Tích của tất cả các số nhỏ hơn và nguyên tố cùng nhau với sẽ đồng dư với (ngoại trừ trường hợp thì bằng ).
(Chi tiết này thường xuất hiện khi ta gom nhóm các phần tử để tính ).
const int mod = 27; // M = p^q (VD: 3^3 = 27)
const int p = 3; // p
long long fact_exclude[mod];
void init() {
fact_exclude[0] = 1;
FOR(i, 1, mod) {
if(i % p != 0) {
fact_exclude[i] = (fact_exclude[i - 1] * i) % mod;
} else {
fact_exclude[i] = fact_exclude[i - 1];
}
}
}
ll mod_inv(ll a, ll m) {
ll x, y;
ll g = extended_euclid(a, m, x, y);
if(g != 1) return -1;
return (x % m + m) % m;
}
ll legendre_(ll n, ll p) {
ll res = 0;
while (n) {
res += n / p;
n /= p;
}
return res;
}
ll bin_pow(ll a, ll b, ll m) {
ll res = 1;
a = a % m;
while(b) {
if(b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
ll extended_wilson(ll n, int p, int mod) {
if (n == 0) return 1; // 0! = 1
// số chu kỳ (Blocks)
ll blocks = n / mod;
// định lý Wilson Mở rộng (xử lý dấu)
ll res = bin_pow(fact_exclude[mod - 1], blocks, mod);
// bù phần lẻ (n % mod) (tức chưa hoàn chỉnh 1 chu kỳ toàn vẹn)
res = (res * fact_exclude[n % mod]) % mod;
// bỏ p và đệ quy tiếp
return (res * extended_wilson(n / p, p, mod)) % mod;
}
ll comb(ll n, ll k, int p) {
if (n < k) return 0;
// tìm q sao cho p^q = mod
int q = 0; int tmp = mod;
while (tmp % p == 0) {
q++;
tmp /= p;
}
ll e = legendre_(n, p) - legendre_(k, p) - legendre_(n - k, p); // lấy số lượng p
if (e >= q) return 0;
ll A = extended_wilson(n, p, mod);
ll B = extended_wilson(k, p, mod);
ll C = extended_wilson(n - k, p, mod);
ll invB = mod_inv(B, mod);
ll invC = mod_inv(C, mod);
if (invB == -1 || invC == -1) return 0;
ll res = A * invB % mod * invC % mod;
res = (res * bin_pow(p, e, mod)) % mod; // bù vào lại số lượng p đã rút ra
return (res + mod) % mod;
}Fibonacci
Bất kỳ dãy số nào tuân theo quy luật đều được định nghĩa hoàn toàn chỉ bằng 2 phần tử đầu tiên là và . Khi 2 truy vấn đè lên nhau, ta chỉ cần cộng các phần tử đầu tiên lại