Hiểu bài toán

Bài toán yêu cầu đếm số lượng số nguyên x trong khoảng từ a đến b (a ≤ x ≤ b) sao cho hiệu số tuyệt đối của x và số đảo ngược của nó (reversed(x)) chia hết cho k. Ví dụ, reversed(123) = 321. Ta cần kiểm tra điều kiện |x - reversed(x)| % k == 0 cho mỗi số x.

Các cách tiếp cận

Cách Brute Force

#include <bits/stdc++.h>
using namespace std;

long long reversed_ll(long long x) {
    long long r = 0;
    while (x > 0) {
        r = r * 10 + (x % 10);
        x /= 10;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b, k;
    cin >> a >> b >> k;
    long long cnt = 0;
    for (long long x = a; x <= b; x++) {
        long long rev = reversed_ll(x);
        if ( llabs(x - rev) % k == 0 ) cnt++;
    }
    cout << cnt;
    return 0;
}

• Time Complexity: O(N * D) (N là số lượng số trong đoạn [a, b], D là số lượng chữ số, ~D <= 7)
• Space Complexity: O(1)

Phương pháp này duyệt qua từng số x từ a đến b. Với mỗi x, ta tính số đảo ngược của nó bằng cách lặp lại phép chia và nhân với 10. Sau đó kiểm tra xem hiệu số tuyệt đối có chia hết cho k hay không. Với b <= 2*10^6, số lần lặp là khoảng 2 triệu, và mỗi lần lặp xử lý rất nhanh (tối đa 7 chữ số), nên phương pháp này hoàn toàn khả thi trong thời gian cho phép.

Cách Brute Force (String)

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

int check(int x) {
    string y = to_string(x);
    string s = "";
    for (int i = y.size() - 1; i >= 0; i--){
        s = s + y[i];
    }
    return stoi(s);
}

int main() {
    int a, b, k, dem = 0;
    cin >> a >> b >> k;

    for (int i = a; i <= b; i++){
        if (abs(i - check(i)) % k == 0)  
            dem++;  
    }

    cout << dem;
    return 0;
}

• Time Complexity: O(N * D)
• Space Complexity: O(D)

Gần giống với phương pháp số 1, nhưng cách này sử dụng chuỗi (string) để đảo ngược số. Số x được chuyển sang string, đảo ngược string đó, rồi chuyển lại về số. Cách này dễ đọc và dễ hiểu hơn nhưng có thể chậm hơn một chút do chi phí thao tác chuỗi và chuyển đổi kiểu dữ liệu, tuy nhiên với ràng buộc của bài toán thì vẫn chạy trong thời gian chấp nhận được.

Cách Optimization (Nếu cần)

#include <iostream>
using namespace std;

int main() {
    // Trong bài này với b <= 2e6 thì Brute Force là đủ.
    // Tuy nhiên, nếu b lớn hơn (ví dụ 10^9), ta cần tối ưu.
    // Nhận xét: |x - rev(x)| có tính chất đặc biệt.
    // Ví dụ: 123 - 321 = -198.
    // 1000 - 0001 = 999.
    // Ta có thể nhận thấy hiệu số là bội của 9.
    // (x - rev(x)) chia hết cho 9.
    // Do đó, nếu k không phải là bội của 9, hoặc k chia hết cho 9 nhưng có thừa số nguyên tố khác, ta có thể lọc.
    // Nhưng với b <= 2e6, code dưới đây là tối ưu nhất về tốc độ code và dễ hiểu.
    // Logic tương tự Solution 1, tối ưu hóa biến và kiểu dữ liệu.
    // Giả sử ta chỉ cần đếm, không cần tối ưu thêm.

    long long a, b, k;
    cin >> a >> b >> k;
    long long cnt = 0;
    for (long long x = a; x <= b; ++x) {
        long long t = x, rev = 0;
        while (t > 0) {
            rev = rev * 10 + t % 10;
            t /= 10;
        }
        if ((x - rev) % k == 0 || (rev - x) % k == 0) cnt++; // Dùng abs hoặc tách đều được
    }
    cout << cnt;
    return 0;
}

• Time Complexity: O(N * D)
• Space Complexity: O(1)

Với ràng buộc b ≤ 2×10^6, Brute Force trực tiếp là phương pháp tốt nhất vì dễ cài đặt và chạy nhanh (khoảng 14 triệu thao tác cơ bản). Nếu b lớn hơn (ví dụ 10^9), Brute Force sẽ bị TLE. Khi đó ta cần sử dụng quy hoạch động hoặc nhận xét toán học. Tuy nhiên, bài toán này chỉ yêu cầu xử lý dữ liệu nhỏ, nên Brute Force là đủ.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Với b ≤ 2×10^6, số lượng số cần kiểm tra là khá nhỏ (2 triệu), nên giải thuật duyệt tuần tự (Brute Force) có độ phức tạp O(N) là hoàn toàn khả thi.
• Hàm đảo ngược số có thể được cài đặt hiệu quả bằng phép toán số học (chia và nhân với 10) thay vì xử lý chuỗi để tăng tốc độ.

Lỗi thường gặp

• Sử dụng biến số nguyên (int) cho các số lớn: Với b = 2×10^6, các phép tính không quá lớn, nhưng để an toàn và tránh lỗi tràn số khi b tăng lên, nên dùng kiểu long long cho các biến liên quan đến giá trị số và hiệu số.
• Xử lý số 0 và số có chữ số 0 ở cuối (ví dụ 120 -> 021 -> 21): Hàm đảo ngược số học chuẩn xác sẽ tự động bỏ các số 0 ở đầu (ví dụ 120 % 10 = 0 -> vòng lặp tiếp theo lấy 12 % 10 = 2...), nên kết quả là 21 như yêu cầu. Cần đảm bảo hàm đảo ngược của bạn xử lý đúng trường hợp này.