Đếm số trong khoảng [L,R] có hiệu với số đảo ngược chia hết cho K C++

Cho khoảng [L, R] và số K. Đếm số x ∈ [L, R] sao cho |x - reverse(x)| chia hết cho K.

Ví dụ minh họa

Ví dụ 1:

• Input: L = 21, R = 25, K = 6
• Output: 2
• Giải thích: 22: |22-22|=0 chia hết 6. 24: |24-42|=18 chia hết 6.

Ví dụ 2:

• Input: L = 11, R = 15, K = 5
• Output: 1
• Giải thích: Chỉ 11: |11-11|=0 chia hết 5.

Mã nguồn C++

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

int countNumbers(int l, int r, int k) {
    int count = 0;
    for (int i = l; i <= r; i++) {
        int num = i, rev = 0, rem;
        while (num > 0) {
            rem = num % 10;
            rev = rev * 10 + rem;
            num /= 10;
        }
        if (abs(i - rev) % k == 0) count++;
    }
    return count;
}

int main() {
    int L = 18, R = 24, K = 6;
    cout << "So thoa man: " << countNumbers(L, R, K);
    return 0;
}

Kết quả chạy chương trình

So thoa man: 4

Độ phức tạp

• Thời gian: O((R-L+1) × log₁₀R) - duyệt khoảng và đảo số.
• Không gian: O(1).

Tối ưu hóa cho khoảng lớn (Digit DP)

Với R ≤ 10¹⁸, không thể duyệt tuần tự. Sử dụng Digit DP đếm số thỏa mãn điều kiện modulo.

Trạng thái DP: dp[pos][tight][mod][started]

• pos: vị trí chữ số đang xét
• tight: đã chạm giới hạn trên chưa
• mod: giá trị hiện tại của (số - đảo số) mod K
• started: đã bắt đầu số (bỏ qua leading zeros)

Độ phức tạp: O(log R × K × 2 × 2) - rất nhanh với K nhỏ.

Lưu ý

• Hàm abs() cần <cstdlib> hoặc <cmath>.
• Số 0: reverse(0) = 0, |0-0|=0 chia hết mọi K.
• Số kết thúc bằng 0: reverse(120) = 21 (không phải 021).