Đếm các số chẵn trong khoảng [L, R] có tổng chữ số chia hết cho 3 trong C++

Cho hai số L và R xác định một khoảng [L, R]. Mục tiêu là tìm tất cả các số trong khoảng này thỏa mãn hai điều kiện: là số chẵn và tổng các chữ số của nó chia hết cho 3.

Ví dụ minh họa

Ví dụ 1:

• Input: L = 10, R = 20
• Output: 2
• Giải thích: Các số chẵn từ 10 đến 20: 10, 12, 14, 16, 18, 20. Trong đó chỉ có 12 (1+2=3) và 18 (1+8=9) có tổng chữ số chia hết cho 3.

Ví dụ 2:

• Input: L = 100, R = 108
• Output: 2
• Giải thích: Các số chẵn: 100, 102, 104, 106, 108. Chỉ 102 (1+0+2=3) và 108 (1+0+8=9) thỏa mãn.

Thuật toán

1. Hàm Digit_sum(int num) tính tổng các chữ số của một số nguyên.
2. Hàm divisible_3(int first, int last) duyệt qua tất cả các số trong khoảng [first, last], kiểm tra nếu số chẵn và tổng chữ số chia hết cho 3 thì tăng bộ đếm.
3. Trả về số lượng tìm được.

Mã nguồn C++

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

int Digit_sum(int num) {
    int total = 0;
    while (num != 0) {
        total += num % 10;
        num = num / 10;
    }
    return total;
}

int divisible_3(int first, int last) {
    int count = 0;
    for (int i = first; i <= last; i++) {
        if (i % 2 == 0 && Digit_sum(i) % 3 == 0) {
            count++;
        }
    }
    return count;
}

int main() {
    int first = 300, last = 500;
    cout << "So luong so chan co tong chu so chia het cho 3: " << divisible_3(first, last);
    return 0;
}

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

So luong so chan co tong chu so chia het cho 3: 34

Độ phức tạp

• Thời gian: O((R-L+1) * log₁₀(R)) - duyệt qua khoảng và tính tổng chữ số.
• Không gian: O(1) - chỉ dùng biến đếm và biến tạm.

Lưu ý: Với khoảng lớn, có thể tối ưu bằng kỹ thuật Dynamic Programming trên chữ số (Digit DP) để giảm độ phức tạp xuống O(log R).