CHUYÊN ĐỀ SỐ HỌC THUẬT TOÁN (ALGORITHMIC NUMBER THEORY)

Mục tiêu:

• Nắm vững các khái niệm và thuật toán Số học cơ bản.
• Hiểu và vận dụng thành thạo các định lý, kỹ thuật nâng cao trong môi trường modulo.
• Nhận diện và giải quyết các bài toán ứng dụng Số học trong các kỳ thi lập trình.

LỜI MỞ ĐẦU

Số học, một trong những nhánh toán học cổ xưa nhất, lại đóng một vai trò quan trọng và đầy bất ngờ trong thế giới Tin học hiện đại, đặc biệt là trong lĩnh vực lập trình thi đấu (Competitive Programming). Từ các kỳ thi học sinh giỏi quốc gia (HSG QG), các vòng loại khu vực ICPC cho đến các kỳ thi online trên Codeforces hay AtCoder, các bài toán liên quan đến Số học luôn xuất hiện với tần suất đáng kể.

Đôi khi, Số học là công cụ chính để tối ưu hóa thuật toán, biến một lời giải "trâu bò" hay thành một lời giải thanh lịch hoặc . Ví dụ kinh điển là việc tính tổng một cấp số cộng: thay vì dùng vòng lặp, ta áp dụng công thức toán học. Trong các trường hợp khác, Số học lại là trái tim của bài toán, đòi hỏi thí sinh phải có kiến thức sâu về các định lý, các thuật toán kiểm tra số nguyên tố, phân tích thừa số, hay xử lý các phép toán trên các số cực lớn thông qua đồng dư thức.

Chuyên đề này được biên soạn nhằm cung cấp một lộ trình học tập có hệ thống, đi từ những viên gạch nền tảng nhất như Thuật toán Euclid, Sàng Eratosthenes cho đến các công cụ mạnh mẽ như Nghịch đảo Modulo, Định lý Euler, Định lý Thặng dư Trung Hoa và các ứng dụng của chúng trong bài toán tổ hợp. Lộ trình học tập được đề xuất như sau:

1. Nắm vững Phần I: Đây là những kiến thức bắt buộc, là nền tảng cho mọi chủ đề sau này.
2. Làm chủ Phần II: Đây là phần cốt lõi của Số học thi đấu, đặc biệt là các kỹ thuật trong môi trường modulo.
3. Luyện tập với Phần III: Vận dụng lý thuyết vào các bài toán kinh điển để xây dựng kỹ năng nhận diện và giải quyết vấn đề.
4. Thử thách bản thân với Phần IV: Rèn luyện với các bài tập từ dễ đến khó trên các nền tảng thực tế.

Với sự kiên trì và một phương pháp học tập đúng đắn, bạn hoàn toàn có thể làm chủ chuyên đề quan trọng này và biến Số học thành một lợi thế của mình trong các kỳ thi sắp tới.

PHẦN I: NỀN TẢNG SỐ HỌC CƠ BẢN (FOUNDATION)

Mục tiêu: Xây dựng nền tảng vững chắc, nắm bắt các công cụ cốt lõi.

A. Ước chung lớn nhất (GCD) và Bội chung nhỏ nhất (LCM)

1. Định nghĩa:

   • Ước số (Divisor): Số nguyên a là ước của số nguyên b nếu b chia hết cho a (ký hiệu a | b).
   • Bội số (Multiple): Số nguyên b là bội của số nguyên a nếu b là ước của a.
   • Ước chung (Common Divisor): Số nguyên d là ước chung của a và b nếu d vừa là ước của a, vừa là ước của b.
   • Ước chung lớn nhất (Greatest Common Divisor - GCD): Là số nguyên dương lớn nhất trong tập hợp các ước chung của a và b. Ký hiệu: gcd(a, b) hoặc (a, b).

2. Thuật toán Euclid tìm GCD:

   • Ý tưởng: Dựa trên nhận xét rằng một số là ước chung của a và b khi và chỉ khi nó cũng là ước chung của b và phần dư a % b. Do đó, ta có tính chất quan trọng:
     Quá trình này lặp lại cho đến khi một trong hai số bằng 0, khi đó GCD chính là số còn lại.
   • Chứng minh tính đúng đắn (trực quan): Gọi d = gcd(a, b). Khi đó a và b đều chia hết cho d. Vì a = q*b + (a % b), nên a % b = a - q*b. Do a và q*b đều chia hết cho d, a % b cũng chia hết cho d. Vậy d là ước chung của b và a % b. Ta có thể chứng minh tương tự theo chiều ngược lại, do đó tập ước chung của (a, b) và (b, a % b) là như nhau, dẫn đến GCD của chúng cũng bằng nhau.
   • Cài đặt:
     • Đệ quy:

       int gcd_recursive(int a, int b) {
           if (b == 0) {
               return a;
           }
           return gcd_recursive(b, a % b);
       }
       

       Copy
     • Không đệ quy (Lặp):

       int gcd_iterative(int a, int b) {
           while (b) {
               a %= b;
               std::swap(a, b);
           }
           return a;
       }
       

       Copy
   • Độ phức tạp: Độ phức tạp của thuật toán Euclid là . Theo Định lý Lamé, số bước của thuật toán không bao giờ vượt quá 5 lần số chữ số của số nhỏ hơn (trong hệ cơ số 10).
   • Hàm std::gcd trong C++17: Từ C++17, có thể dùng hàm std::gcd trong thư viện <numeric>.

     #include <iostream>
     #include <numeric> // Required for std::gcd
     
     int main() {
         int a = 54, b = 24;
         std::cout << "GCD of " << a << " and " << b << " is " << std::gcd(a, b) << std::endl;
         return 0;
     }
     

     Copy

3. Bội chung nhỏ nhất (LCM):

   • Công thức tính thông qua GCD:

   • Lưu ý về tràn số: Phép nhân a * b có thể gây tràn số đối với các kiểu dữ liệu cơ bản (int, long long) trước khi thực hiện phép chia. Để tránh điều này, ta nên cài đặt công thức một cách an toàn hơn:

   • Code mẫu:

     long long lcm(long long a, long long b) {
         if (a == 0 || b == 0) return 0;
         return (a / std::gcd(a, b)) * b;
     }
     

     Copy

B. Số Nguyên Tố và Phân Tích Thừa Số Nguyên Tố

1. Định nghĩa:

   • Số nguyên tố (Prime Number): Là số tự nhiên lớn hơn 1 và chỉ có hai ước số dương là 1 và chính nó.
   • Hợp số (Composite Number): Là số tự nhiên lớn hơn 1 không phải là số nguyên tố.
   • Định lý cơ bản của Số học (Fundamental Theorem of Arithmetic): Mọi số nguyên lớn hơn 1 đều có thể được biểu diễn một cách duy nhất (không kể thứ tự) dưới dạng tích của các số nguyên tố. Ví dụ: .

2. Kiểm tra tính nguyên tố (Primality Test):

   • Phương pháp duyệt ngây thơ O(n): Duyệt tất cả các số từ 2 đến n-1, nếu có số nào là ước của n thì n là hợp số.
   • Phương pháp tối ưu: Duyệt đến sqrt(n):
     • Giải thích: Nếu n là hợp số, nó có thể được viết dưới dạng n = a * b. Nếu cả a và b đều lớn hơn sqrt(n), thì a * b > sqrt(n) * sqrt(n) = n, vô lý. Do đó, ít nhất một trong hai ước a hoặc b phải nhỏ hơn hoặc bằng sqrt(n). Ta chỉ cần duyệt tìm ước đến sqrt(n).
   • Code mẫu và phân tích độ phức tạp:

     bool is_prime(int n) {
         if (n <= 1) return false;
         for (int i = 2; i * i <= n; ++i) {
             if (n % i == 0) {
                 return false;
             }
         }
         return true;
     }
     // Độ phức tạp: O(sqrt(n))
     

     Copy

3. Phân tích thừa số nguyên tố (Prime Factorization):

   • Phương pháp duyệt đến sqrt(n): Ta lặp qua các số i từ 2 đến sqrt(n). Nếu i là ước của n, ta đếm xem i xuất hiện bao nhiêu lần trong phân tích và chia n cho i đến khi không chia hết nữa. Sau vòng lặp, nếu n vẫn còn lớn hơn 1, thì phần còn lại của n chính là một thừa số nguyên tố.
   • Code mẫu và phân tích độ phức tạp:

     #include <vector>
     #include <map>
     
     // Phân tích ra map<thừa số, số mũ>
     std::map<int, int> factorize(int n) {
         std::map<int, int> factors;
         for (int i = 2; i * i <= n; ++i) {
             while (n % i == 0) {
                 factors[i]++;
                 n /= i;
             }
         }
         if (n > 1) {
             factors[n]++;
         }
         return factors;
     }
     // Độ phức tạp: O(sqrt(n))
     

     Copy

4. Sàng Eratosthenes (Sieve of Eratosthenes):

   • Mục đích: Tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng N một cách hiệu quả.

   • Ý tưởng: Bắt đầu với một danh sách tất cả các số từ 2 đến N. Lần lượt lấy số nguyên tố p nhỏ nhất chưa được xét. Đánh dấu tất cả các bội của p (như 2p, 3p, 4p, ...) là hợp số. Lặp lại quá trình này với số nguyên tố tiếp theo. Những số không bị đánh dấu cuối cùng là số nguyên tố. Một tối ưu quan trọng là bắt đầu đánh dấu từ p*p, vì các bội nhỏ hơn của p (như 2p, 3p) đã được đánh dấu bởi các số nguyên tố nhỏ hơn p (như 2, 3).

   • Cài đặt sàng cơ bản:

     #include <vector>
     
     std::vector<bool> sieve_eratosthenes(int N) {
         std::vector<bool> is_prime(N + 1, true);
         is_prime[0] = is_prime[1] = false;
         for (int p = 2; p * p <= N; ++p) {
             if (is_prime[p]) {
                 for (int i = p * p; i <= N; i += p)
                     is_prime[i] = false;
             }
         }
         return is_prime;
     }
     

     Copy

   • Độ phức tạp: .

   • Biến thể nâng cao:

     • Sàng tuyến tính (Linear Sieve): Thuật toán này đảm bảo mỗi hợp số chỉ bị đánh dấu đúng một lần bởi ước nguyên tố nhỏ nhất của nó. Điều này giúp giảm độ phức tạp xuống còn .
     • Sàng tìm ước nguyên tố nhỏ nhất (Smallest Prime Factor - SPF): Biến thể này không chỉ đánh dấu số nguyên tố/hợp số mà còn lưu lại ước nguyên tố nhỏ nhất (SPF) của mỗi số. Sau khi sàng xong, ta có thể phân tích thừa số nguyên tố của bất kỳ số n <= N trong thời gian bằng cách liên tục chia n cho spf[n].

     // Sàng tuyến tính kết hợp tìm SPF
     #include <vector>
     const int MAXN = 1000000;
     std::vector<int> primes;
     int spf[MAXN + 1];
     
     void linear_sieve(int N) {
         for (int i = 2; i <= N; ++i) {
             if (spf[i] == 0) {
                 spf[i] = i;
                 primes.push_back(i);
             }
             for (int p : primes) {
                 if (p > spf[i] || (long long)i * p > N) {
                     break;
                 }
                 spf[i * p] = p;
             }
         }
     }
     
     // Phân tích T_S_N_T nhanh sau khi sàng
     std::map<int, int> fast_factorize(int n) {
         std::map<int, int> factors;
         while (n != 1) {
             factors[spf[n]]++;
             n /= spf[n];
         }
         return factors;
     }
     // Độ phức tạp sàng: O(N)
     // Độ phức tạp mỗi truy vấn phân tích: O(log n)
     

     Copy

PHẦN II: SỐ HỌC NÂNG CAO VÀ ĐỒNG DƯ THỨC (MODULAR ARITHMETIC)

Mục tiêu: Trang bị các công cụ mạnh để giải quyết các bài toán với số lớn.

A. Đồng dư thức (Modular Arithmetic)

1. Định nghĩa: Hai số nguyên a và b được gọi là đồng dư với nhau theo modulo m (với m là số nguyên dương) nếu chúng có cùng số dư khi chia cho m. Ký hiệu:

   Điều này tương đương với (a - b) chia hết cho m.

2. Các phép toán cơ bản:

   • Cộng:
   • Trừ: (Cộng thêm m để đảm bảo kết quả không âm).
   • Nhân:

3. Lũy thừa nhanh (Binary Exponentiation / Exponentiation by Squaring):

   • Mục đích: Tính trong .
   • Ý tưởng: Dựa trên biểu diễn nhị phân của số mũ b.
     • Nếu b là số chẵn, .
     • Nếu b là số lẻ, . Ta lặp lại quá trình này, giảm b đi một nửa ở mỗi bước, cho đến khi b = 0.
   • Code mẫu:

     long long power(long long base, long long exp, long long mod) {
         long long res = 1;
         base %= mod;
         while (exp > 0) {
             if (exp % 2 == 1) res = (res * base) % mod;
             base = (base * base) % mod;
             exp /= 2;
         }
         return res;
     }
     

     Copy

B. Nghịch đảo Modulo (Modular Inverse)

1. Định nghĩa: Nghịch đảo modulo của a theo modulo m là một số nguyên x sao cho:

   Ký hiệu: . Phép chia (a / b) mod m được thực hiện bằng cách tính (a * b⁻¹) mod m.

2. Điều kiện tồn tại: Nghịch đảo modulo của a theo m tồn tại khi và chỉ khi a và m là hai số nguyên tố cùng nhau, tức là .

3. Phương pháp tìm nghịch đảo:

   • Khi m là số nguyên tố: Dùng Định lý Fermat nhỏ: Nếu m là số nguyên tố và a không chia hết cho m, ta có:

     Suy ra:

     Vậy . Ta có thể tính bằng Lũy thừa nhanh.

   • Khi m là hợp số (trường hợp tổng quát): Dùng Thuật toán Euclid mở rộng (Extended Euclidean Algorithm).

     • Ý tưởng: Thuật toán này tìm cặp số nguyên (x, y) sao cho:
       Nếu , ta có . Lấy modulo m cả hai vế:
       Khi đó, x chính là nghịch đảo modulo của a. Giá trị x trả về có thể âm, ta cần chuẩn hóa nó về khoảng [1, m-1] bằng cách (x % m + m) % m.
     • Code mẫu cho Euclid mở rộng:

       // Trả về gcd(a, b) và gán giá trị cho x, y
       long long extended_gcd(long long a, long long b, long long &x, long long &y) {
           if (a == 0) {
               x = 0;
               y = 1;
               return b;
           }
           long long x1, y1;
           long long d = extended_gcd(b % a, a, x1, y1);
           x = y1 - (b / a) * x1;
           y = x1;
           return d;
       }
       
       // Tìm nghịch đảo modulo
       long long mod_inverse(long long a, long long m) {
           long long x, y;
           long long g = extended_gcd(a, m, x, y);
           if (g != 1) {
               // Nghịch đảo không tồn tại
               return -1;
           }
           return (x % m + m) % m;
       }
       

       Copy

C. Các Định Lý Quan Trọng

1. Định lý Fermat nhỏ (Fermat's Little Theorem): Đã phát biểu và ứng dụng ở trên.

2. Hàm phi Euler (Euler's Totient Function):

   • Định nghĩa: (phi của n) là số các số nguyên dương nhỏ hơn hoặc bằng n và nguyên tố cùng nhau với n. Ví dụ: vì có 6 số {1, 2, 4, 5, 7, 8} nguyên tố cùng nhau với 9.
   • Công thức tính: Nếu phân tích thừa số nguyên tố của n là , thì:

3. Định lý Euler (Euler's Totient Theorem):

   • Phát biểu: Nếu , thì:

   • Đây là sự tổng quát hóa của Định lý Fermat nhỏ. Khi m là số nguyên tố p, thì , và định lý Euler trở thành định lý Fermat nhỏ. Định lý này cho phép tìm nghịch đảo modulo của a theo m (kể cả khi m là hợp số) bằng công thức , nhưng yêu cầu phải tính được .

D. Phương trình Diophantine tuyến tính

1. Dạng phương trình: , với a, b, c là các số nguyên đã biết, và cần tìm nghiệm nguyên (x, y).

2. Định lý Bezout: Phương trình có nghiệm nguyên (x, y) khi và chỉ khi c chia hết cho d = gcd(a, b).

3. Cách tìm một nghiệm:

   • Sử dụng thuật toán Euclid mở rộng để tìm x_0, y_0 cho phương trình .
   • Nếu c chia hết cho d, thì một nghiệm riêng (x', y') của phương trình ban đầu là:

4. Cách tìm tất cả các nghiệm: Từ một nghiệm riêng (x', y'), tập hợp tất cả các nghiệm của phương trình được cho bởi công thức:

   với k là một số nguyên bất kỳ.

PHẦN III: CÁC BÀI TOÁN ỨNG DỤNG KINH ĐIỂN

Mục tiêu: Rèn luyện kỹ năng nhận diện và áp dụng lý thuyết vào giải toán.

A. Bài toán về Ước số

1. Đếm số lượng ước của một số n:

   • Dựa trên phân tích thừa số nguyên tố .
   • Một ước bất kỳ của n sẽ có dạng với .
   • Với mỗi , số mũ có thể có cách chọn (từ 0 đến ).
   • Công thức: Số lượng ước, ký hiệu hoặc :

2. Tính tổng các ước của một số n:

   • Công thức: Tổng các ước, ký hiệu :
     Mỗi tổng trong ngoặc là tổng của một cấp số nhân: .

B. Bài toán Tổ hợp liên quan đến chia hết

1. Tính Tổ hợp chập k của n () modulo m:

   • Trường hợp m là số nguyên tố:
     • Công thức: .
     • Tính toán: Ta không thể thực hiện phép chia trực tiếp trong môi trường modulo. Thay vào đó, ta chuyển nó thành phép nhân với nghịch đảo modulo:

     • Yêu cầu: Cần tính trước (precompute) các giá trị giai thừa n! và nghịch đảo modulo của các giai thừa (n!)⁻¹ theo modulo m. Nghịch đảo có thể tính bằng Định lý Fermat nhỏ vì m là số nguyên tố.

       const int MAXN = 100000;
       const int MOD = 1e9 + 7;
       long long fact[MAXN + 1];
       long long invFact[MAXN + 1];
       
       // Hàm lũy thừa nhanh power() đã định nghĩa ở trên
       
       long long modInverse(long long n) {
           return power(n, MOD - 2, MOD);
       }
       
       void precompute() {
           fact[0] = 1;
           for (int i = 1; i <= MAXN; i++) {
               fact[i] = (fact[i - 1] * i) % MOD;
           }
           invFact[MAXN] = modInverse(fact[MAXN]);
           for (int i = MAXN - 1; i >= 0; i--) {
               invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
           }
       }
       
       long long nCk_mod_p(int n, int k) {
           if (k < 0 || k > n) return 0;
           return (((fact[n] * invFact[k]) % MOD) * invFact[n - k]) % MOD;
       }
       

       Copy
   • Trường hợp m là hợp số:
     • Định lý Lucas: Khi cần tính với p là số nguyên tố và n, k lớn, Định lý Lucas cho phép chia nhỏ bài toán. Nếu biểu diễn của n và k trong cơ số p là và , thì:

     • Khi m là hợp số: Ta phân tích m thành các thừa số nguyên tố dạng . Ta tính theo từng modulo . Cuối cùng, dùng Định lý Thặng dư Trung Hoa (Chinese Remainder Theorem - CRT) để tìm ra kết quả cuối cùng theo modulo m. Việc tính phức tạp hơn và thường yêu cầu xử lý cẩn thận các thừa số p trong giai thừa.

2. Các bài toán đếm khác: Nhiều bài toán đếm trong quy hoạch động hoặc tổ hợp có các ràng buộc chia hết. Ví dụ: "Đếm số dãy con có tổng chia hết cho K", "Đếm số cách tô màu một đồ thị sao cho số đỉnh màu X chia hết cho 3". Các bài toán này thường được giải quyết bằng cách mở rộng trạng thái của quy hoạch động để lưu thêm thông tin về số dư (state, remainder).

PHẦN IV: BÀI TẬP LUYỆN TẬP

• Nhóm 1: Nhận biết - Thông hiểu (Cơ bản)

  • Bài tập chỉ yêu cầu cài đặt trực tiếp các thuật toán đã học.
  • Ví dụ:
    • Codeforces - 791A (Bear and Big Brother) - Bài tập làm quen
    • Codeforces - 231A (Team) - Bài tập làm quen
    • "Cho A, B, M, tính " (Lũy thừa nhanh).
    • "Cho N, tìm tất cả các số nguyên tố không vượt quá N" (Sàng Eratosthenes).
    • "Cho hai số A, B, tìm ước chung lớn nhất và bội chung nhỏ nhất" (GCD, LCM).

• Nhóm 2: Vận dụng (Trung bình)

  • Bài tập yêu cầu kết hợp 1-2 khái niệm hoặc biến đổi nhẹ.
  • Ví dụ:
    • Codeforces - 271A (Beautiful Year) - Duyệt và kiểm tra tính chất
    • Codeforces - 472A (Design Tutorial: Learn from Math) - Sàng, tìm cặp số
    • "Tính " (Tổ hợp modulo số nguyên tố).
    • "Đếm số ước của N!" (Dùng công thức Legendre).
    • "Tìm nghiệm nguyên dương nhỏ nhất của phương trình ax + by = c" (Phương trình Diophantine).
    • Codeforces - 1352C (K-th Not Divisible by n) - Phân tích toán học, tìm kiếm nhị phân.

• Nhóm 3: Vận dụng cao (Nâng cao)

  • Bài toán kết hợp Số học với các chuyên đề khác (Quy hoạch động, Đồ thị, ...).
  • Bài toán đòi hỏi nhận xét toán học sâu sắc, sử dụng các định lý, thuật toán nâng cao.
  • Ví dụ:
    • "Đếm số dãy con có tổng chia hết cho K" (Quy hoạch động với modulo).
    • Codeforces - 1108D (Diverse Garland) - Quy hoạch động đơn giản
    • Các bài toán yêu cầu dùng Định lý Lucas, CRT, hoặc Miller-Rabin, Pollard's Rho.
    • Các bài toán đếm phức tạp sử dụng công thức đảo ngược Möbius.
    • AtCoder DP Contest - G (Longest Path) - Quy hoạch động trên đồ thị.

• Nguồn bài tập gợi ý:

  • VNOI: wiki.vnoi.info và oj.vnoi.info
  • Codeforces: codeforces.com/problemset (lọc theo tag number theory, math, combinatorics)
  • AtCoder: atcoder.jp/contests (đặc biệt là các kỳ thi Beginner và Regular)
  • Topcoder: topcoder.com/community/data-science/data-science-tutorials (các bài viết hướng dẫn chất lượng cao).

PHỤ LỤC

A. Code Template

Dưới đây là mã nguồn C++ sạch, có chú thích cho các thuật toán quan trọng.

#include <iostream>
#include <vector>
#include <numeric> // For std::gcd in C++17
#include <map>

// --- PHẦN I: CƠ BẢN ---

// Thuật toán Euclid lặp
long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

// Bội chung nhỏ nhất
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return std::abs(a * b) / gcd(a, b);
    // An toàn hơn: return (a / gcd(a, b)) * b;
}

// Kiểm tra số nguyên tố O(sqrt(n))
bool is_prime(long long n) {
    if (n <= 1) return false;
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

// Sàng tìm ước nguyên tố nhỏ nhất (SPF)
// Cần gọi linear_sieve(MAXN) trước khi dùng
const int MAXN_SIEVE = 1000001;
std::vector<int> primes;
int spf[MAXN_SIEVE];

void linear_sieve(int N) {
    for (int i = 2; i <= N; ++i) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || (long long)i * p > N) break;
            spf[i * p] = p;
        }
    }
}

// --- PHẦN II: NÂNG CAO ---

// Lũy thừa nhanh (Binary Exponentiation)
long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (__int128)res * base % mod;
        base = (__int128)base * base % mod;
        exp /= 2;
    }
    return res;
}

// Thuật toán Euclid mở rộng
// Trả về gcd(a, b) và gán giá trị cho x, y thỏa mãn ax + by = gcd(a, b)
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    long long x1, y1;
    long long d = extended_gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

// Nghịch đảo modulo
long long mod_inverse(long long a, long long m) {
    long long x, y;
    long long g = extended_gcd(a, m, x, y);
    if (g != 1) return -1; // Nghịch đảo không tồn tại
    return (x % m + m) % m;
}

// --- PHẦN III: ỨNG DỤNG ---

// Tổ hợp C(n, k) modulo số nguyên tố p
// Cần gọi precompute() trước khi dùng
const int MAXN_COMB = 100001;
const int MOD = 1e9 + 7;
long long fact[MAXN_COMB];
long long invFact[MAXN_COMB];

void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN_COMB; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    invFact[MAXN_COMB - 1] = power(fact[MAXN_COMB - 1], MOD - 2, MOD);
    for (int i = MAXN_COMB - 2; i >= 0; i--) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

long long nCk_mod_p(int n, int k) {
    if (k < 0 || k > n) return 0;
    return (((fact[n] * invFact[k]) % MOD) * invFact[n - k]) % MOD;
}

B. Bảng Tóm Tắt