Khóa học CTDL và GT

Bài 4.5. Bài tập tổng hợp về modulo và phép chia

Chào mừng trở lại với chuỗi bài blog về Cấu trúc dữ liệu và Giải thuật!

Trong thế giới lập trình, có những công cụ tưởng chừng rất đơn giản nhưng lại mang trong mình sức mạnh khổng lồ. Hôm nay, chúng ta sẽ đi sâu vào hai trong số những công cụ ấy: phép chia số nguyên (/) và toán tử modulo (%). Đây không chỉ là các phép tính cơ bản, mà còn là nền tảng để giải quyết vô số bài toán từ đơn giản đến phức tạp, đặc biệt là trong lĩnh vực giải thuật và các bài toán lập trình thi đấu.

Bài viết này không chỉ ôn lại lý thuyết mà còn tập trung vào các bài tập tổng hợp để bạn thấy được sự linh hoạt và ứng dụng rộng rãi của chúng. Hãy cùng khám phá!

Ôn lại lý thuyết cơ bản: Chia và Modulo

Trước khi đi vào các bài tập, hãy cùng nhắc lại một chút về hai toán tử này trong ngữ cảnh của C++ (và hầu hết các ngôn ngữ lập trình khác khi xử lý số nguyên):

1. Phép chia số nguyên (/): Khi bạn chia hai số nguyên, kết quả trả về sẽ là phần nguyên của phép chia thực tế. Phần thập phân sẽ bị cắt bỏ (truncated). Ví dụ:

   • 10 / 3 kết quả là 3.
   • 7 / 2 kết quả là 3.
   • -10 / 3 kết quả là -3. (Hành vi làm tròn về 0).

2. Toán tử Modulo (%): Toán tử này trả về phần dư của phép chia số nguyên. Mối quan hệ giữa phép chia và modulo là: a = (a / b) * b + (a % b). Ví dụ:

   • 10 % 3 kết quả là 1. (10 = 3 * 3 + 1)
   • 7 % 2 kết quả là 1. (7 = 3 * 2 + 1)
   • -10 % 3 kết quả là -1. (-10 = -3 * 3 + -1)

Lưu ý về dấu của kết quả modulo: Trong C++, kết quả của a % b sẽ có cùng dấu với a (số bị chia). Điều này quan trọng khi làm việc với số âm. Trong nhiều bài toán, chúng ta chỉ quan tâm đến kết quả modulo không âm. Nếu a % b trả về giá trị âm r, bạn có thể chuyển nó sang không âm bằng cách cộng thêm b: (r + b) % b.

Tại sao Modulo và Phép chia lại quan trọng?

Sự quan trọng của hai toán tử này nằm ở khả năng:

• Kiểm tra tính chia hết: a % b == 0 nghĩa là a chia hết cho b.
• Trích xuất chữ số: Sử dụng % 10 để lấy chữ số cuối cùng và / 10 để bỏ chữ số cuối cùng của một số.
• Xử lý các bài toán có tính chu kỳ: Ví dụ như các ngày trong tuần, giờ trong ngày, vị trí trong mảng tròn (circular array).
• Thu nhỏ kết quả phép tính lớn (Modular Arithmetic): Giúp tránh tràn số (overflow) khi thực hiện các phép tính với các số rất lớn, một kỹ thuật không thể thiếu trong lý thuyết số và các bài toán mật mã, tổ hợp.
• Tạo chỉ mục (Indexing): Thường dùng trong băm (hashing) hoặc quản lý bộ đệm vòng.

Giờ thì, hãy cùng đi vào các ví dụ cụ thể để thấy rõ điều này!

Các dạng bài tập tổng hợp và ví dụ minh họa (C++)

Chúng ta sẽ xem xét một số dạng bài tập phổ biến sử dụng kết hợp phép chia và modulo.

Dạng 1: Kiểm tra tính chất của số

Đây là dạng cơ bản nhất.

Bài toán ví dụ 1.1: Kiểm tra số chẵn/lẻ. Kiểm tra xem một số nguyên n có phải là số chẵn hay không.

#include <iostream>

int main() {
    int n;
    std::cout << "Nhap mot so nguyen: ";
    std::cin >> n;

    // Mot so chan chia het cho 2, tuc la phan du bang 0
    if (n % 2 == 0) {
        std::cout << n << " la so chan." << std::endl;
    } else {
        std::cout << n << " la so le." << std::endl;
    }

    return 0;
}

Giải thích: Toán tử % 2 sẽ trả về 0 nếu n chia hết cho 2 (là số chẵn) và trả về 1 (hoặc -1 nếu n âm) nếu n không chia hết cho 2 (là số lẻ). Điều kiện n % 2 == 0 là cách tiêu chuẩn và hiệu quả để kiểm tra tính chẵn lẻ.

Dạng 2: Trích xuất và xử lý các chữ số của một số

Phép chia / 10 và modulo % 10 là cặp đôi hoàn hảo để làm việc với từng chữ số của một số nguyên.

Bài toán ví dụ 2.1: Tính tổng các chữ số của một số nguyên dương. Cho một số nguyên dương n, tính tổng của tất cả các chữ số tạo nên n.

#include <iostream>

int main() {
    int n;
    std::cout << "Nhap mot so nguyen duong: ";
    std::cin >> n;

    int original_n = n; // Luu lai so ban dau de in ket qua dep
    int sum_of_digits = 0;

    // Vong lap nay chay cho den khi n tro thanh 0
    while (n > 0) {
        // Buoc 1: Trich xuat chu so cuoi cung
        int last_digit = n % 10;

        // Buoc 2: Cong chu so vua trich vao tong
        sum_of_digits += last_digit;

        // Buoc 3: Loai bo chu so cuoi cung khoi so n
        n = n / 10;
    }

    std::cout << "Tong cac chu so cua " << original_n << " la: " << sum_of_digits << std::endl;

    return 0;
}

Giải thích:

• Vòng lặp while (n > 0) đảm bảo chúng ta xử lý tất cả các chữ số từ phải sang trái.
• n % 10: Lấy phần dư khi chia cho 10, đây chính là chữ số ở hàng đơn vị.
• n / 10: Lấy phần nguyên khi chia cho 10, điều này hiệu quả loại bỏ chữ số ở hàng đơn vị và dịch các chữ số còn lại sang phải.
• Quá trình này lặp lại cho đến khi n bằng 0, tức là không còn chữ số nào để xử lý.

Bài toán ví dụ 2.2: Đếm số chữ số của một số nguyên dương. Sử dụng ý tưởng tương tự, chúng ta có thể đếm số chữ số.

#include <iostream>

int main() {
    int n;
    std::cout << "Nhap mot so nguyen duong: ";
    std::cin >> n;

    if (n == 0) { // Truong hop dac biet: so 0 co 1 chu so
        std::cout << "So " << n << " co 1 chu so." << std::endl;
        return 0;
    }

    int original_n = n;
    int count_digits = 0;

    // Vong lap chay cho den khi n tro thanh 0
    while (n > 0) {
        // Chi can loai bo chu so, khong can lay gia tri
        n = n / 10;
        count_digits++; // Moi lan loai bo 1 chu so thi tang bo dem
    }

    std::cout << "So " << original_n << " co " << count_digits << " chu so." << std::endl;

    return 0;
}

Giải thích: Logic vẫn là dùng phép chia / 10 để "bóc" từng chữ số ra. Thay vì cộng giá trị chữ số vào tổng, chúng ta chỉ đơn giản là tăng một bộ đếm (count_digits) mỗi lần thực hiện phép chia / 10.

Dạng 3: Bài toán có tính chu kỳ (Cyclic Problems)

Nhiều vấn đề trong thực tế có tính chất lặp đi lặp lại theo một chu kỳ nhất định (ví dụ: 7 ngày trong tuần, 12 tháng trong năm, 60 giây trong phút). Toán tử modulo % là chìa khóa để giải quyết các bài toán này.

Bài toán ví dụ 3.1: Tính ngày trong tuần sau N ngày. Nếu hôm nay là thứ start_day (với Chủ Nhật là 0, Thứ Hai là 1, ..., Thứ Bảy là 6), hỏi sau N ngày nữa là thứ mấy?

#include <iostream>
#include <vector>
#include <string>

int main() {
    std::vector<std::string> days = {"Chu Nhat", "Thu Hai", "Thu Ba", "Thu Tu", "Thu Nam", "Thu Sau", "Thu Bay"};

    int start_day; // 0 cho Chu Nhat, 1 cho Thu Hai, ..., 6 cho Thu Bay
    long long N; // So ngay sau do (co the lon)

    std::cout << "Nhap ngay bat dau (0-6, 0=CN, 1=T2, ...): ";
    std::cin >> start_day;

    std::cout << "Nhap so ngay sau do: ";
    std::cin >> N;

    // Tong so buoc chuyen dich tu ngay bat dau
    // Lay modulo 7 vi chu ky ngay trong tuan la 7
    int end_day_index = (start_day + N) % 7;

    // Xu ly truong hop ket qua am neu start_day hoac N co the am (mac du bai toan thuong N duong)
    // Trong C++, (-10 % 7) la -3. De chuyen ve ket qua duong tu 0 den 6:
    if (end_day_index < 0) {
        end_day_index += 7;
    }


    std::cout << "Sau " << N << " ngay nua la ngay: " << days[end_day_index] << std::endl;

    return 0;
}

Giải thích:

• Chúng ta có 7 ngày trong một chu kỳ.
• Tổng số bước "tiến" từ ngày bắt đầu là N.
• Thay vì tính ngày cuối cùng bằng cách cộng thẳng start_day + N (có thể ra số rất lớn), chúng ta nhận thấy rằng cứ sau mỗi 7 ngày, ngày trong tuần lại lặp lại.
• Do đó, chúng ta chỉ cần quan tâm đến phần dư của tổng số bước chia cho 7: (start_day + N) % 7. Kết quả này sẽ nằm trong phạm vi 0 đến 6, tương ứng với các ngày trong tuần sau N ngày.
• Phần xử lý if (end_day_index < 0) cần thiết nếu có khả năng start_day + N là một số âm mà phần dư % 7 trong C++ lại cho kết quả âm. Cộng thêm 7 đảm bảo kết quả cuối cùng nằm trong dải 0 đến 6.

Dạng 4: Phân tích thời gian hoặc đơn vị đo lường

Chuyển đổi giữa các đơn vị lớn và nhỏ thường sử dụng cả phép chia và modulo.

Bài toán ví dụ 4.1: Chuyển đổi tổng số giây sang giờ, phút, giây. Cho tổng số giây total_seconds, chuyển đổi nó thành định dạng Giờ:Phút:Giây.

#include <iostream>

int main() {
    long long total_seconds;
    std::cout << "Nhap tong so giay: ";
    std::cin >> total_seconds;

    // 1 gio = 3600 giay
    long long hours = total_seconds / 3600;

    // So giay con lai sau khi tinh gio
    long long remaining_seconds_after_hours = total_seconds % 3600;

    // 1 phut = 60 giay
    long long minutes = remaining_seconds_after_hours / 60;

    // So giay con lai sau khi tinh phut
    long long seconds = remaining_seconds_after_hours % 60;

    std::cout << total_seconds << " giay tuong duong voi: ";
    std::cout << hours << " gio, " << minutes << " phut, " << seconds << " giay." << std::endl;

    return 0;
}

Giải thích:

• Chúng ta dùng phép chia total_seconds / 3600 để lấy số giờ nguyên.
• Sau đó, dùng modulo total_seconds % 3600 để lấy số giây còn lại sau khi đã bóc tách số giờ.
• Với số giây còn lại này, chúng ta lại dùng phép chia / 60 để lấy số phút nguyên.
• Cuối cùng, dùng modulo % 60 trên số giây còn lại sau khi bóc tách phút để lấy số giây cuối cùng. Đây là một mẫu hình phổ biến để chuyển đổi từ một đơn vị nhỏ tích lũy (tổng giây) sang các đơn vị lớn hơn (giờ, phút, giây) bằng cách kết hợp chia và modulo.

Dạng 5: Giới thiệu về Số học Module (Modular Arithmetic)

Trong các bài toán cần xử lý với các số rất lớn, kết quả có thể vượt quá khả năng lưu trữ của các kiểu dữ liệu tiêu chuẩn (int, long long). Số học module cung cấp một cách để thực hiện các phép tính (cộng, trừ, nhân) trong một phạm vi giới hạn bằng cách lấy modulo sau mỗi bước hoặc áp dụng các tính chất của module.

Tính chất cơ bản nhất:

• (a + b) % m = ((a % m) + (b % m)) % m
• (a - b) % m = ((a % m) - (b % m) + m) % m (cộng thêm m để đảm bảo kết quả không âm)
• (a * b) % m = ((a % m) * (b % m)) % m

Bài toán ví dụ 5.1: Tính (A + B) % M với A, B có thể rất lớn. Giả sử A và B là hai số nguyên dương rất lớn, tính (A + B) % M mà không sợ bị tràn số khi tính A + B.

#include <iostream>

int main() {
    long long A, B, M; // Su dung long long de co the chua so lon hon int

    std::cout << "Nhap A: ";
    std::cin >> A;
    std::cout << "Nhap B: ";
    std::cin >> B;
    std::cout << "Nhap M (modulo): ";
    std::cin >> M;

    // Cach 1: Tinh truc tiep A + B, co the gay tran so neu A va B rat lon
    // long long sum = A + B;
    // long long result1 = sum % M;
    // std::cout << "Ket qua tinh truc tiep: " << result1 << std::endl; // Co the sai

    // Cach 2: Ap dung tinh chat cua so hoc module de tranh tran so
    // (A + B) % M = ((A % M) + (B % M)) % M
    long long a_mod_m = A % M;
    long long b_mod_m = B % M;

    long long sum_mod = (a_mod_m + b_mod_m) % M;

    // Xu ly truong hop ket qua cuoi cung co the am do phep cong a_mod_m + b_mod_m
    if (sum_mod < 0) {
        sum_mod += M;
    }

    std::cout << "Ket qua su dung so hoc module: " << sum_mod << std::endl;

    return 0;
}

Giải thích:

• Nếu A và B rất lớn (ví dụ, gần bằng giới hạn trên của long long), tổng A + B có thể vượt quá khả năng lưu trữ của long long và gây ra tràn số.
• Cách 2 sử dụng tính chất (A + B) % M = ((A % M) + (B % M)) % M. Chúng ta lấy modulo của từng số hạng A và B trước khi cộng. Vì A % M và B % M chắc chắn nhỏ hơn M (và nhỏ hơn A, B ban đầu), tổng (A % M) + (B % M) sẽ nhỏ hơn nhiều so với A + B ban đầu, giảm đáng kể nguy cơ tràn số (trừ khi M cũng cực kỳ lớn). Cuối cùng, chúng ta lấy modulo M một lần nữa để có kết quả cuối cùng trong phạm vi [0, M-1] (hoặc [0, M)).
• Lưu ý lại phần xử lý kết quả âm nếu có, mặc dù với các số dương A, B, M, kết quả (a_mod_m + b_mod_m) % M thường không âm trừ khi một trong các số hạng trung gian là âm hoặc M âm (điều ít xảy ra trong các bài toán phổ thông).

Bài tập ví dụ:

Tổng hàm Euler

Trong một dự án xây dựng mới, FullHouse Dev đang phải đối mặt với một bài toán thú vị về lý thuyết số. Họ cần tính toán tổng của một chuỗi các giá trị đặc biệt dựa trên hàm phi Euler.

Bài toán

Cho một số nguyên dương \(N\). Hàm phi Euler \(\phi(n)\) đếm số lượng số nguyên dương nhỏ hơn hoặc bằng \(n\) mà nguyên tố cùng nhau với \(n\). Định nghĩa hàm \(F(N)\) là tổng của \(\phi(i)\) với \(i\) chạy từ \(1\) đến \(N\). Nhiệm vụ của FullHouse Dev là tính giá trị của \(F(N)\) theo modulo \(10^9 + 7\).

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Mỗi test case gồm một dòng chứa một số nguyên dương \(N\).

OUTPUT FORMAT:

• Với mỗi test case, in ra một dòng duy nhất chứa giá trị của \(F(N)\) sau khi chia lấy dư cho \(10^9 + 7\).

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq N \leq 10^6\)

Ví dụ

INPUT

2
2
3

OUTPUT

3
11

Giải thích

• Test case 1: \(N = 2\)
  • \(F(2) = \phi(1) + \phi(2) = 1 + 1 = 3\)
• Test case 2: \(N = 3\)
  • \(F(3) = \phi(1) + \phi(2) + \phi(3) = 1 + 1 + 2 = 4\) Chào bạn,

Đây là hướng dẫn giải bài "Tổng hàm Euler" một cách hiệu quả, phù hợp với ràng buộc của bài toán (N lên đến $10^6$, T lên đến $10^5$).

Ý tưởng chính:

Bài toán yêu cầu tính tổng của hàm phi(i) từ 1 đến N cho nhiều giá trị N. Vì số lượng test case T lớn nhưng giá trị lớn nhất của N lại tương đối nhỏ ($10^6$), đây là dấu hiệu rõ ràng cho thấy chúng ta cần tính toán trước (precompute) các giá trị cần thiết và sau đó trả lời mỗi truy vấn N một cách nhanh chóng.

Cụ thể, chúng ta cần tính:

1. Giá trị của hàm phi(i) cho tất cả i từ 1 đến giá trị N lớn nhất có thể (ở đây là $10^6$).
2. Tổng tiền tố (prefix sum) của các giá trị phi(i) đã tính.

Các bước thực hiện:

1. Khởi tạo:

   • Xác định giá trị N_max lớn nhất có thể ($10^6$).
   • Tạo một mảng (ví dụ: phi_values) có kích thước N_max + 1 để lưu giá trị phi(i) cho i từ 0 đến N_max.
   • Tạo một mảng khác (ví dụ: prefix_sum) có kích thước N_max + 1 để lưu tổng tiền tố F(i) = sum(phi(j)) từ j=1 đến i.
   • Định nghĩa hằng số MOD = 10^9 + 7.

2. Tính toán hàm phi(i) cho tất cả i từ 1 đến N_max:

   • Cách hiệu quả nhất để làm điều này cho một dải số là sử dụng một biến thể của Sàng Eratosthenes.
   • Ban đầu, gán phi_values[i] = i cho tất cả i từ 1 đến N_max. (Ghi nhớ phi(1) = 1).
   • Lặp từ p = 2 đến N_max.
   • Nếu phi_values[p] vẫn bằng p, điều đó có nghĩa p là một số nguyên tố.
     • Đối với số nguyên tố p, phi(p) = p - 1. Cập nhật phi_values[p] = p - 1.
     • Đối với tất cả các bội số j của p (tức là j = 2*p, 3*p, ...) lên đến N_max, p là một ước nguyên tố của j. Chúng ta có thể cập nhật phi_values[j] bằng công thức phi(j) = phi(j) * (1 - 1/p), điều này tương đương với phi_values[j] = phi_values[j] / p * (p - 1). Trong lập trình, cách hiệu quả và an toàn hơn (tránh chia số lớn rồi nhân lại) là sử dụng phi_values[j] -= phi_values[j] / p.
   • Cách này tính được tất cả giá trị phi(i) lên đến N_max trong độ phức tạp gần O(N log log N).

3. Tính tổng tiền tố:

   • Khởi tạo prefix_sum[0] = 0.
   • Lặp từ i = 1 đến N_max:
     • prefix_sum[i] = (prefix_sum[i-1] + phi_values[i]) % MOD.
     • Đảm bảo kết quả luôn dương nếu phép cộng có thể làm giá trị tạm thời âm (mặc dù với phi luôn dương và MOD dương, bước này có thể bỏ qua trừ khi prefix_sum[i-1] hoặc phi_values[i] có thể âm, điều không xảy ra ở đây).

4. Xử lý truy vấn:

   • Đọc số lượng test case T.
   • Lặp T lần:
     • Đọc giá trị N cho test case hiện tại.
     • Kết quả là giá trị đã được tính sẵn trong mảng tổng tiền tố: prefix_sum[N]. In giá trị này.

Tóm tắt các cấu trúc dữ liệu và thuật toán cần dùng:

• Mảng: Hai mảng để lưu giá trị phi(i) và tổng tiền tố F(i).
• Thuật toán: Một biến thể của Sàng Eratosthenes để tính đồng thời tất cả các giá trị phi(i) lên đến giới hạn cho trước. Sau đó là tính tổng tiền tố đơn giản.
• Phép toán: Phép chia lấy dư (modulo) tại mỗi bước cộng vào tổng tiền tố để tránh tràn số.

Làm thêm nhiều bài tập miễn phí tại đây